¡La Unión Nacional de Clubes Universitarios de Programación finalmente ha lanzado la sonda espacial UCPC 1! Esta sonda viaja por el espacio mostrando en un panel electrónico una secuencia y consultas, símbolos de la resolución de problemas algorítmicos.

El panel electrónico está dividido en $N$ celdas, y en cada celda se muestra un número entero. Esta secuencia cambia a una secuencia diferente cada medianoche; en la celda $i$-ésima se muestra el valor más grande entre los números que estaban en las celdas $l_i, l_i+1, \dots, r_i$ el día anterior.

Desafortunadamente, la UCPC 1 no pudo completar su exploración con éxito y está siendo succionada hacia una singularidad tras cruzar el horizonte de sucesos de un agujero negro. En el momento en que llega a la singularidad, en cada celda del panel se muestra el número más grande entre aquellos que aparecen infinitas veces en esa celda a medida que transcurre un tiempo infinito.

Determina el estado del panel electrónico de la UCPC 1 al llegar a la singularidad.

Entrada

La primera línea contiene el número de celdas $N$. ($1 \le N \le 300\,000$)

La segunda línea contiene los números inicialmente mostrados en cada celda $a_1, \dots, a_N$, separados por espacios. ($1 \le a_i \le N$; todos los $a_i$ son enteros)

Desde la tercera línea, se proporcionan $N$ líneas, cada una con $l_i, r_i$ separados por espacios. ($1 \le l_i \le r_i \le N$)

Salida

Imprime, en orden, los números que se muestran en cada celda del panel cuando la UCPC 1 llega a la singularidad.

Ejemplos

Entrada 1

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

Salida 1

4 3 3 4

Nota

La secuencia mostrada es, sucesivamente, $[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$.