Painting

Time Limit : 3 sec, Memory Limit : 524288 KB

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