시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 256 MB0000.000%

문제

Kanade has a sequence $A_{1...n}$ and $m$ intervals $[L_i, R_i]$ of indices from $1$ to $n$, bounds included. He does $m$ operations in sequence, one for each interval. For the $i$-th operation, Kanade can choose and perform one of the following two actions:

  1. Choose $x \in [L_i, R_i]$ and update $A_x := A_x + 1$.
  2. Rearrange $A_{L_i...R_i}$ in any order Kanade wants.

Now Kanade wants to know the maximum value of $A_{k}$ after these operations. Find the answer for each $k \in [1, n]$.

입력

The first line of input contains two integers $n$ and $m$, the size of the sequence and the number of operations ($1 \leq n, m \leq 2 \cdot 10^5$). The second line contains $n$ integers $A_{1...n}$, the initial sequence ($0 \leq A_i \leq 2 \cdot 10^5$).

Then follow $m$ lines. The $i$-th of them contains two integers $L_i$ and $R_i$ describing the respective interval ($1 \leq L_i \leq R_i \leq n$).

출력

Output $n$ integers, the $i$-th of which is the maximum possible value of $A_{i}$ after $m$ operations.

예제 입력 1

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

예제 출력 1

2 4 3 2