La Fédération des clubs de programmation universitaires a enfin lancé la sonde spatiale UCPC 1 ! Cette sonde voyage dans l'espace en affichant sur son panneau d'affichage une suite et des requêtes, symboles de la résolution de problèmes algorithmiques.

Le panneau d'affichage est divisé en $N$ cases, et chaque case affiche un entier. Cette suite change chaque jour à minuit : la $i$-ième case affiche la valeur maximale parmi les nombres qui étaient affichés dans les cases $l_i, l_i+1, \dots, r_i$ la veille.

Malheureusement, la sonde UCPC 1 n'a pas pu terminer sa mission avec succès et est aspirée vers une singularité après avoir franchi l'horizon des événements d'un trou noir. Au moment où elle atteint la singularité, chaque case du panneau affiche le plus grand nombre parmi ceux qui y apparaissent une infinité de fois au fil d'un temps infini.

Déterminez l'état du panneau d'affichage de la sonde UCPC 1 lorsqu'elle atteint la singularité.

Entrée

La première ligne contient le nombre de cases $N$ ($1 \le N \le 300\,000$).

La deuxième ligne contient les nombres initialement affichés dans chaque case $a_1, \dots, a_N$, séparés par des espaces ($1 \le a_i \le N$ ; tous les $a_i$ sont des entiers).

À partir de la troisième ligne, $N$ lignes suivent, chacune contenant $l_i$ et $r_i$ séparés par un espace ($1 \le l_i \le r_i \le N$).

Sortie

Affichez, dans l'ordre, les nombres affichés dans chaque case du panneau lorsque la sonde UCPC 1 atteint la singularité.

Exemples

Entrée 1

4
1 2 3 4
3 4
3 3
2 3
1 2

Sortie 1

4 3 3 4

Remarque

Les suites affichées sont successivement $[1, 2, 3, 4]$, $[4, 3, 3, 2]$, $[3, 3, 3, 4]$, $[4, 3, 3, 3]$, $[3, 3, 3, 4]$, $[4, 3, 3, 3]$, $\dots$