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;

vector<long long int> q;
long long int pre[100001];

long long int t[100001];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,Q;
	cin>>n>>Q;
	q.emplace_back(n);
	for(int i=1;i<=Q;i++){
		long long int x;
		cin>>x;
		while(!q.empty()&&x<=q.back())	q.pop_back();
		q.emplace_back(x);
	}
	int now=q.size()-1;
	t[now]=1;
	while(now>=0){
		long long int k=q[now];
		while(k>0){
			int x=lower_bound(q.begin(),q.end(),k)-q.begin();
			x--;
			if(x==-1)	break;
			t[x]+=k/q[x]*t[now];
			k%=q[x];
		}
		pre[1]+=t[now];pre[1+k]-=t[now];
		now--;
	}
	for(int i=1;i<=n;i++)
		pre[i]+=pre[i-1];
	for(int i=1;i<=n;i++)
		cout<<pre[i]<<'\n';
}