23134번 - Interval Shuffle 다국어

문제

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.

제한

힌트