Kanade 有一个长度为 $n$ 的序列 $A_{1 \dots n}$ 和 $m$ 个区间 $[L_i, R_i]$，下标范围为 $1$ 到 $n$（包含边界）。他按顺序执行 $m$ 次操作，每次操作对应一个区间。对于第 $i$ 次操作，Kanade 可以选择并执行以下两种动作之一：

1. 选择 $x \in [L_i, R_i]$ 并执行 $A_x := A_x + 1$。
2. 将 $A_{L_i \dots R_i}$ 重排为他想要的任意顺序。

现在 Kanade 想知道在这些操作之后，$A_k$ 的最大可能值。请对每个 $k \in [1, n]$ 求出该值。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示序列的长度和操作次数 ($1 \le n, m \le 2 \cdot 10^5$)。第二行包含 $n$ 个整数 $A_{1 \dots n}$，表示初始序列 ($0 \le A_i \le 2 \cdot 10^5$)。

接下来 $m$ 行，第 $i$ 行包含两个整数 $L_i$ 和 $R_i$，描述对应的区间 ($1 \le L_i \le R_i \le n$)。

输出格式

输出 $n$ 个整数，其中第 $i$ 个整数表示在 $m$ 次操作后 $A_i$ 的最大可能值。

样例

输入 1

4 3
0 1 0 1
2 4
1 3
2 3

输出 1

2 4 3 2