Ассоциация студенческих клубов программирования наконец запустила космический зонд UCPC-1! Этот зонд путешествует по космосу, отображая на своем табло последовательности и запросы — символы решения алгоритмических задач.

Табло разделено на $N$ ячеек, в каждой из которых отображается одно целое число. Эта последовательность меняется каждую полночь: в $i$-й ячейке отображается максимальное из чисел, которые были в ячейках с $l_i$ по $r_i$ в предыдущий день.

К сожалению, зонд UCPC-1 не смог успешно завершить свою миссию, пересек горизонт событий черной дыры и затягивается в сингулярность. В момент достижения сингулярности в каждой ячейке табло будет отображаться наибольшее из чисел, которые бесконечное количество раз появляются в этой ячейке при стремлении времени к бесконечности.

Давайте определим состояние табло зонда UCPC-1 в момент достижения сингулярности.

Входные данные

В первой строке дано количество ячеек $N$ ($1 \le N \le 300\,000$).

Во второй строке через пробел даны числа $a_1, \dots, a_N$, изначально отображенные в ячейках ($1 \le a_i \le N$; все $a_i$ — целые числа).

С третьей строки следуют $N$ строк, в каждой из которых через пробел даны $l_i$ и $r_i$ ($1 \le l_i \le r_i \le N$).

Выходные данные

Выведите числа, которые будут отображаться в каждой ячейке табло, когда зонд UCPC-1 достигнет сингулярности.

Примеры

Входные данные 1

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

Выходные данные 1

4 3 3 4

Примечание

Последовательности чисел, отображаемые на табло, меняются следующим образом: $[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$