#agc003e. [agc003_e]Sequential operations on Sequence

[agc003_e]Sequential operations on Sequence

問題文

高橋君はお母さんから数列をもらいました。この数列の長さは NN で、i(1iN)i(1 ≦ i ≦ N) 項目の要素は ii です。 高橋君は、この数列に以下の操作を合計で QQ 回行いました。ii 番目の操作は、パラメータ qiq_i であらわされ、以下のように行われます。

  • いまの数列を無限回繰り返した数列の先頭 qiq_i 項をとって、新たな数列とする。

QQ 回の操作後、この数列に 11 から NN までの各々の数が何回ずつ現れるかを求めてください。

制約

  • 1N1051 ≦ N ≦ 10^5
  • 0Q1050 ≦ Q ≦ 10^5
  • 1qi10181 ≦ q_i ≦ 10^{18}
  • 入力はすべて整数である。

入力

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

NN QQ q1q_1 : qQq_Q

出力

NN 行出力せよ。i(1iN)i(1 ≦ i ≦ N) 行目には、QQ 回の操作後の数列にあらわれる数 ii の個数を表す整数ひとつを出力せよ。


入力例 1

5 3
6
4
11

出力例 1

3
3
3
2
0

11 回目の操作で、数列は 1,2,3,4,5,11,2,3,4,5,1 となります。

22 回目の操作で、数列は 1,2,3,41,2,3,4 となります。

33 回目の操作で、数列は 1,2,3,4,1,2,3,4,1,2,31,2,3,4,1,2,3,4,1,2,3 となります。 この数列には 1,2,3,4,51,2,3,4,5 がそれぞれ 3,3,3,2,03,3,3,2,0 個含まれているので、上のように出力します。


入力例 2

10 10
9
13
18
8
10
10
9
19
22
27

出力例 2

7
4
4
3
3
2
2
2
0
0