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>
#define int long long
using namespace std;

const int MAXN = 1e5 + 7; 
 
int n, q, z[MAXN];
vector<int> v;
map<int, int> mp;
 
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> q;
	v.push_back(n);
	for (int i = 0; i < q; i++) {
		int f;
		cin >> f;
		while (!v.empty() && v.back() >= f) v.pop_back();
		v.push_back(f);
	}
	reverse(v.begin(), v.end());
	mp[v[0]] = 1;
	for (int i = 0; i < (int)v.size(); i++) {
		int a = v[i];
		while (a > v.back()) {
			int tmp = *--upper_bound(v.rbegin(), v.rend() - i - 1, a);
			mp[tmp] += mp[v[i]] * (a / tmp);
			a %= tmp;
		}
		z[a] += mp[v[i]];
	}
	for (int i = MAXN - 2; ~i; i--) z[i] = z[i] + z[i + 1];
	for (int i = 1; i <= n; i++) cout << z[i] << '\n';
	return 0;
}