Problem Statement

You are given a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ and length-$M$ integer sequences $L=(L_1,L_2,\ldots,L_M)$ and $R=(R_1,R_2,\ldots,R_M)$.

For this permutation $P$, perform the following operation for $i=1,2,\ldots,M$ in this order:

• Among $P_{L_i},P_{L_i+1},\ldots,P_{R_i}$, swap the positions of the element with the minimum value and the element with the maximum value.

Find each element of $P$ after the $M$ operations.

Constraints

• $2\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $P$ is a permutation of $(1,2,\ldots,N)$.
• $1\le L_i < R_i\le N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$ $M$
• $P_1$ $P_2$ $\ldots$ $P_N$
• $L_1$ $R_1$
• $L_2$ $R_2$
• $\vdots$
• $L_M$ $R_M$

Output

Output each element of $P$ after the $M$ operations, in order from front to back, separated by spaces.

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

3 4 2 5 1

Initially, $P=(3,1,4,2,5)$.

• For $i=1$: among $P_1,P_2,P_3$, the minimum value is $P_2$ and the maximum value is $P_3$. Swapping $P_2$ and $P_3$ gives $P=(3,4,1,2,5)$.
• For $i=2$: among $P_1,P_2,P_3,P_4,P_5$, the minimum value is $P_3$ and the maximum value is $P_5$. Swapping $P_3$ and $P_5$ gives $P=(3,4,5,2,1)$.
• For $i=3$: among $P_1,P_2,P_3,P_4$, the minimum value is $P_4$ and the maximum value is $P_3$. Swapping $P_3$ and $P_4$ gives $P=(3,4,2,5,1)$.

After the three operations, $P=(3,4,2,5,1)$.

6 7
3 6 5 2 4 1
4 5
2 3
3 5
4 6
3 4
1 6
3 5

3 5 4 6 2 1

• Source: AtCoder ABC 476 E