题目描述

给定一个 $(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$ 的各个元素。

输入格式

输入按以下格式从标准输入读入：

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

输出格式

将执行完 $M$ 次操作后的排列 $P$ 的各个元素，从前到后以空格分隔，输出在一行。

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

3 4 2 5 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)$。

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

数据范围

• $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$

• 所有输入值均为整数。

• 来源：AtCoder ABC 476 E

子任务设置

• 子任务 1（30 分）：$N,M\le 2000$。
• 子任务 2（30 分）：$N\le 2\times 10^5$ 且 $M\le 2000$。
• 子任务 3（40 分）：无特殊限制。