题目描述

给定 $(1, 2, \ldots, N)$ 的一个排列 $P = (P_1, P_2, \ldots, P_N)$，以及两个长度为 $M$ 的整数序列 $L = (L_1, \ldots, L_M)$ 和 $R = (R_1, \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 ... P_N
L_1 R_1
L_2 R_2
...
L_M R_M

输出格式

在一行中输出 $M$ 次操作结束后的 $P_1, P_2, \ldots, P_N$，相邻两数之间用一个空格隔开。

输入示例 1

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

输出示例 1

3 4 2 5 1

示例 1 说明

初始时 $P = (3, 1, 4, 2, 5)$。

• $i = 1$：$P_1, P_2, P_3$ 中最小值在 $P_2$、最大值在 $P_3$，交换后 $P = (3, 4, 1, 2, 5)$；
• $i = 2$：$P_1 \sim P_5$ 中最小值在 $P_3$、最大值在 $P_5$，交换后 $P = (3, 4, 5, 2, 1)$；
• $i = 3$：$P_1 \sim P_4$ 中最小值在 $P_4$、最大值在 $P_3$，交换后 $P = (3, 4, 2, 5, 1)$。

注意第 $3$ 次操作里最大值在左、最小值在右——交换与两者的先后位置无关。

输入示例 2

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

输出示例 2

3 5 4 6 2 1

示例 2 说明

$M > N$，同一个区间（如 $[3,5]$）被操作了两次，但两次之间 $P$ 已经变了，所以两次的结果并不相同。这说明每次操作都必须基于当时的 $P$ 重新查询最值位置，不能预处理一次了事。

输入示例 3

2 1
2 1
1 2

输出示例 3

1 2

示例 3 说明

$N = 2$ 是允许的最小值，区间 $[1,2]$ 里最小值在 $P_2$、最大值在 $P_1$，交换后变成 $(1,2)$。由于约束保证 $L_i < R_i$，区间长度至少为 $2$，最小值和最大值一定是两个不同的位置，不存在「自己和自己交换」的情况。

约束条件

• $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$
• 所有输入值均为整数