Difference Array Practice

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$.

You must support $q$ operations. Each operation gives an interval $[l, r]$ and adds $1$ to $a_l, a_{l+1}, \dots, a_r$.

Find what the whole sequence becomes at the end.

Input Format

The first line contains two integers $n, q$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$.

The following $q$ lines each contain two integers $l, r$.

Output Format

Output one line with $n$ integers, the answer.

Sample Input

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

Sample Output

2 4 6 6 6

Constraints

For $100\%$ of the data: $1 \le n, q \leq 10^5$, $1 \leq a_i \leq 10^5$, $1 \le l \le r \le n$.