在桌子上摆着 $n$ 个盒子，左数第 $i$ 个盒子里初始装着 $a_i$ 颗糖果。

接下来小 P 进行了 $m$ 次操作，每次操作有参数 $l,r$，小 P 可以选择一个操作执行：

1. 在左数第 $l$ 个盒子到第 $r$ 个盒子各放入一颗糖果。
2. 将左数第 $l$ 个盒子到第 $r$ 个盒子任意重排列。

小 P 想知道，所有操作结束之后，每个位置的盒子当中，最多包含了多少糖果。

输入格式

第一行两个整数 $n,m$ 表示盒子数和操作数。

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个盒子初始糖果数。

接下来 $m$ 行每行两个整数 $l,r$ 描述一次操作。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示左数第 $i$ 个盒子中最多有多少糖果。

样例一

input

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

output

5 6 6 5

explanation

解释一种让第 $4$ 个盒子糖果数为 $5$ 的方法：

$(1,2,2,3)\rightarrow(1,3,2,3)\rightarrow(1,4,2,3)\rightarrow(1,2,4,3)\rightarrow(2,3,5,3)\rightarrow(2,3,3,5)$

样例二

见附件下载。

数据范围与提示

对于 $30\%$ 的数据，保证 $n\leq 5,m\leq 3$。

对于 $60\%$ 的数据，保证 $n,m\leq 5000$。

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 5\times 10^5,1\leq a_i\leq 10^9,1\leq l\leq r\leq n$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$