There are $n$ boxes on a table, with the $i$-th box from the left initially containing $a_i$ candies.

Little P performs $m$ operations. Each operation has parameters $l$ and $r$. For each operation, Little P can choose to perform one of the following:

1. Add one candy to each box from the $l$-th to the $r$-th box.
2. Arbitrarily rearrange the candies in the boxes from the $l$-th to the $r$-th box.

Little P wants to know, after all operations are completed, what is the maximum number of candies that can be contained in each box.

Input

The first line contains two integers $n$ and $m$, representing the number of boxes and the number of operations.

The second line contains $n$ integers, where the $i$-th integer $a_i$ represents the initial number of candies in the $i$-th box.

The next $m$ lines each contain two integers $l$ and $r$, describing an operation.

Output

Output a single line containing $n$ integers, where the $i$-th integer represents the maximum number of candies that can be in the $i$-th box.

Examples

Input 1

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

Output 1

5 6 6 5

Note 1

An explanation of a method to make the $4$-th box contain $5$ candies:

$(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)$

Input 2

See attachment.

Constraints

For $30\%$ of the data, $n\leq 5, m\leq 3$.

For $60\%$ of the data, $n, m\leq 5000$.

For $100\%$ of the data, $1\leq n, m\leq 5\times 10^5, 1\leq a_i\leq 10^9, 1\leq l\leq r\leq n$.