AT_abc476_e.Min-Max Swap

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.

给你一个 $(1,2,\ldots,N)$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，以及两个长度为 $M$ 的整数序列 $L=(L_1,L_2,\ldots,L_M)$ 和 $R=(R_1,R_2,\ldots,R_M)$。

对这个排列 $P$，按 $i=1,2,\ldots,M$ 的顺序依次执行以下操作：

• 在子数组 $P_{L_i},P_{L_i+1},\ldots,P_{R_i}$ 中，将最小值元素与最大值元素的位置互换。

求经过 $M$ 次操作后 $P$ 的每个元素。

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$

输入从标准输入中按以下格式给出：

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

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

在执行 $M$ 次操作后，按从前到后的顺序输出 $P$ 的每个元素，元素之间用空格分隔。

Sample 1 Explanation:
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)$.

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.

样例 1 解释：
初始时，$P=(3,1,4,2,5)$。

• 对于 $i=1$：在 $P_1,P_2,P_3$ 中，最小值为 $P_2$，最大值为 $P_3$。交换 $P_2$ 和 $P_3$ 后得到 $P=(3,4,1,2,5)$。
• 对于 $i=2$：在 $P_1,P_2,P_3,P_4,P_5$ 中，最小值为 $P_3$，最大值为 $P_5$。交换 $P_3$ 和 $P_5$ 后得到 $P=(3,4,5,2,1)$。
• 对于 $i=3$：在 $P_1,P_2,P_3,P_4$ 中，最小值为 $P_4$，最大值为 $P_3$。交换 $P_3$ 和 $P_4$ 后得到 $P=(3,4,2,5,1)$。

经过三次操作后，$P=(3,4,2,5,1)$。

约束条件

• $2\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $P$ 是 $(1,2,\ldots,N)$ 的一个排列。
• $1\le L_i < R_i\le N$
• 所有输入值均为整数。