Stowarzyszenie Studenckich Kół Programistycznych w końcu wystrzeliło sondę kosmiczną UCPC 1! Sonda podróżuje przez kosmos, wyświetlając na tablicy świetlnej ciągi liczb i zapytania, które są symbolem rozwiązywania problemów algorytmicznych.

Tablica świetlna podzielona jest na $N$ pól, a w każdym z nich wyświetlona jest jedna liczba całkowita. Ten ciąg zmienia się codziennie o północy w inny ciąg, w którym w $i$-tym polu wyświetlana jest największa wartość spośród liczb, które znajdowały się poprzedniego dnia w polach od $l_i$ do $r_i$ włącznie.

Niestety, sonda UCPC 1 nie zakończyła pomyślnie swojej misji, przekroczyła horyzont zdarzeń czarnej dziury i jest wciągana do osobliwości. W momencie dotarcia do osobliwości, w każdym polu tablicy wyświetlona zostanie największa liczba spośród tych, które pojawiają się w tym polu nieskończenie wiele razy, gdy czas dąży do nieskończoności.

Wyznacz wygląd tablicy świetlnej sondy UCPC 1 w momencie dotarcia do osobliwości.

Wejście

W pierwszej linii podana jest liczba pól $N$ ($1 \le N \le 300\,000$).

W drugiej linii podane są początkowe liczby wyświetlone w każdym polu $a_1, \dots, a_N$, oddzielone spacjami ($1 \le a_i \le N$; wszystkie $a_i$ są liczbami całkowitymi).

Od trzeciej linii, przez kolejne $N$ linii, podane są wartości $l_i, r_i$ oddzielone spacjami ($1 \le l_i \le r_i \le N$).

Wyjście

Wypisz liczby wyświetlone w każdym polu tablicy w momencie, gdy UCPC 1 dotrze do osobliwości.

Przykład

Wejście 1

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

Wyjście 1

4 3 3 4

Uwagi

Wyświetlane ciągi to kolejno: $[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$