B: 三角形足し算

問題

長さ $N$ の数列 $A = (a_1, ..., a_N)$ があり、値は最初全て $0$ である。

数列 $A$ に対して、以下で説明するクエリを $Q$ 回行う。

• 二つの正整数 $l$, $k$ が与えられる。$0 \leq i < k$ を満たす各整数 $i$ に対して $a_{l+i}$ に $i+1$ を加算する。

$Q$ 回のクエリを順に処理した後の数列 $A$ を出力せよ。

入力形式

入力は $Q + 1$ 行で与えられる。

$N$ $Q$
$l_1$ $k_1$
$l_2$ $k_2$
...
$l_Q$ $k_Q$

• $1$ 行目には、数列の長さ $N$ とクエリの数 $Q$ が空白区切りで与えられる。
• 続く $Q$ 行には、各 $l$ と $k$ が空白区切りで与えられる。$l_i$ 及び $k_i$ はそれぞれ $i$ 番目のクエリの $l$ 及び $k$ を表す。

制約

• 入力は全て整数で与えられる
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $2 \leq l_i + k_i \leq N + 1$ ($1\leq i\leq Q$)
• $1 \leq l_i$ ($1\leq i\leq Q$)
• $1 \leq k_i$ ($1\leq i\leq Q$)

出力形式

クエリを処理し終えた後の $A$ の各要素を、$1$ 番目から順番に半角スペース区切りで一行に出力せよ。

入力例1

4 1
2 3

出力例1

0 1 2 3

このクエリにおいて、$A$ の添字 $2 \leq i < 2+3$ の部分が変化する。 まず $a_2$ に $1$ 加算する。 次に $a_3$ に $2$ 加算する。 最後に $a_4$ に $3$ 加算する。 結果、できる数列は $(0, 1, 2, 3)$ である。

入力例2

8 3
1 2
2 4
3 6

出力例2

1 3 3 5 7 4 5 6

入力例3

10 15
1 2
2 3
3 2
3 2
3 2
3 2
3 2
4 3
5 3
5 2
5 2
5 2
7 2
8 2
9 2

出力例3

1 3 7 14 6 11 4 3 3 2

ここにそのような例を載せることはできませんが、オーバーフローには注意してください。

---