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<cstdio>
#define ll long long
const int N=1e5+5;
int n,Q,m,dn,i;
ll d[N],g[N],ans[N];
ll read(){
	char c=getchar();ll k=0;for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;
}
void write(ll x){if (x>9) write(x/10);putchar(x%10+48);}
int find(ll k){
	int l=1,r=dn,m;
	while (l<r){m=l+r+1>>1;
		if (d[m]<=k) l=m; else r=m-1;
	}
	return l;
}
int main(){
	n=read();Q=read();d[dn=1]=n;
	for (;Q--;){ll k=read();
		for (;k<=d[dn];dn--);d[++dn]=k;
	}
	for (m=d[1],g[dn]=1,i=dn;i;i--) if (g[i]){
		ll k=d[i],v=g[i];d[i]++;
		for (;k>m;){
			int x=find(k);
			g[x]+=k/d[x]*v;k%=d[x];
		}
		ans[k]+=v;
	}
	for (i=m-1;i;i--) ans[i]+=ans[i+1];
	for (i=1;i<=n;i++) write(ans[i]),putchar('\n');
}