Problem: Snuke got an integer sequence from his mother, as a birthday present. The sequence has N elements, and the i-th of them is i. Snuke performs the following Q operations on this sequence. The i-th operation, described by a parameter q_i, is as follows:

* Take the first q_i elements from the sequence obtained by concatenating infinitely many copy of the current sequence, then replace the current sequence with those q_i elements.



After these Q operations, find how many times each of the integers 1 through N appears in the final sequence.

Constraints

* 1 ≦ N ≦ 10^5
* 0 ≦ Q ≦ 10^5
* 1 ≦ q_i ≦ 10^{18}
* All input values are integers.

Input

The input is given from Standard Input in the following format:


N Q
q_1
:
q_Q


Output

Print N lines. The i-th line (1 ≦ i ≦ N) should contain the number of times integer i appears in the final sequence after the Q operations.

Examples

Input

5 3
6
4
11


Output

3
3
3
2
0


Input

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


Output

7
4
4
3
3
2
2
2
0
0

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5 + 100;

ll n, q, cnt, l[N], a[N], ans[N];

void input() {
	cin >> n >> q;
	l[cnt++] = n;
	for (int i = 1; i <= q; i++) {
		cin >> l[cnt];
		while (cnt && l[cnt] < l[cnt - 1]) {
			l[cnt - 1] = l[cnt];
			cnt--;
		}
		cnt++;
	}
}

void solve() {
	a[cnt - 1] = 1;
	for (int i = cnt - 1; ~i; i--) {
		ll x = l[i];
		while (x > l[0]) {
			ll y;
			if (x == l[i])
				y = lower_bound(l, l + cnt, x) - l - 1;
			else
				y = upper_bound(l, l + cnt, x) - l - 1;
			a[y] += a[i] * (x / l[y]);
			x %= l[y];
		}
		ans[x] += a[i];
	}
}

void output() {
	for (int i = n; i; i--)
		ans[i] += ans[i + 1];
	for (int i = 1; i <= n; i++)
		cout << ans[i] << ' ';
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	input();
	solve();
	output();
}