[AGC003E] Sequential operations on Sequence

题意翻译

一串数,初始为 $1\sim n$,现在给 $Q$ 个操作,每次操作把数组长度变为 $q_i$,新增的数为上一个操作后的数组的重复。问 $Q$ 次操作后 $1\sim n$ 每个数出现了多少次。

题目描述

[problemUrl]: https://atcoder.jp/contests/agc003/tasks/agc003_e 高橋君はお母さんから数列をもらいました。この数列の長さは $ N $ で、$ i(1\ ≦\ i\ ≦\ N) $ 項目の要素は $ i $ です。 高橋君は、この数列に以下の操作を合計で $ Q $ 回行いました。$ i $ 番目の操作は、パラメータ $ q_i $ であらわされ、以下のように行われます。 - いまの数列を無限回繰り返した数列の先頭 $ q_i $ 項をとって、新たな数列とする。 $ Q $ 回の操作後、この数列に $ 1 $ から $ N $ までの各々の数が何回ずつ現れるかを求めてください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ q_1 $ : $ q_Q $

输出格式


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

输入输出样例

输入样例 #1

5 3
6
4
11

输出样例 #1

3
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

说明

### 制約 - $ 1\ ≦\ N\ ≦\ 10^5 $ - $ 0\ ≦\ Q\ ≦\ 10^5 $ - $ 1\ ≦\ q_i\ ≦\ 10^{18} $ - 入力はすべて整数である。 ### Sample Explanation 1 $ 1 $ 回目の操作で、数列は $ 1,2,3,4,5,1 $ となります。 $ 2 $ 回目の操作で、数列は $ 1,2,3,4 $ となります。 $ 3 $ 回目の操作で、数列は $ 1,2,3,4,1,2,3,4,1,2,3 $ となります。 この数列には $ 1,2,3,4,5 $ がそれぞれ $ 3,3,3,2,0 $ 個含まれているので、上のように出力します。