题目描述

给定一个长度为 $N$ 的排列 $P = (P_1, P_2, \ldots, P_N)$，以及 $M$ 次操作。

每次操作给定两个整数 $L_i, R_i$（$1 \le L_i \le R_i \le N$）。在每次操作中，你需要：

1. 找出区间 $P[L_i \ldots R_i]$ 中的最大值所在的位置 $p_{\max}$，以及最小值所在的位置 $p_{\min}$。
2. 交换 $P[p_{\max}]$ 与 $P[p_{\min}]$。

请输出经过全部 $M$ 次操作后的最终排列 $P$。

输入格式

输入从标准输入中给出，格式如下：

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

输出格式

输出一行，包含 $N$ 个整数，表示最终的排列 $P$，两两之间用空格隔开。

数据范围

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

样例

样例输入 1

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

样例输出 1

1 2 4 3 5

样例解释 1：

• 初始时 $P = (3, 1, 4, 2, 5)$。
• 第 1 次操作区间 $[1, 3]$：最大值为 $4$（位置 3），最小值为 $1$（位置 2）。交换后 $P = (3, 4, 1, 2, 5)$。
• 第 2 次操作区间 $[2, 5]$：最大值为 $5$（位置 5），最小值为 $1$（位置 3）。交换后 $P = (3, 4, 5, 2, 1)$。
• 第 3 次操作区间 $[1, 5]$：最大值为 $5$（位置 3），最小值为 $1$（位置 5）。交换后 $P = (3, 4, 1, 2, 5)$。
• 最终结果输出 1 2 4 3 5。

样例输入 2

1 1
1
1 1

样例输出 2

1

样例输入 3

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

样例输出 3

6 2 3 4 5 1