Problem G: Painting

Problem

長さ$N$の数列$X$が与えられる。初期状態では$X$の要素は全て$0$である。加えて、$M$個の整数のペア$(A_i, B_i)$が与えられる。各ペアに対し以下の操作を行い、最終的な数列$X$を出力せよ。

整数$j$ $(1 \le j \le N)$に対し、$(A_i+j)$を$B_i$で割った余りを$X_j$に加える。

Input

入力は以下の形式で与えられる。

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
:
$A_M$ $B_M$

$1$行目に、与えられる数列の要素数$N$、ペアの数$M$が空白区切りで与えられる。
続く$M$行に、$i$番目のペア$(A_i, B_i)$が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \le N, M \le 10^5$
• $0 \le A_i < B_i \le 10^9 (1 \le i \le M)$
• 与えられる入力は全て整数である

Output

操作後の数列を$N$行で出力せよ。$j$行目に$X_j$を出力せよ。

Sample Input 1

5 3
1 4
3 7
0 1000

Sample Output 1

7
10
9
5
8

Sample Input 2

14 12
1 4
2 3
0 5
1 4
1 2
0 8
0 2
0 10
0 1
0 8
3 10
1 10

Sample Output 2

15
24
25
31
35
44
32
25
24
15
16
25
31
40

Note

Link

 

---