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<iostream>
#include<cstdio>
#define ll long long
const int M=1e5+10;
using namespace std;
int n,m,top;
ll f[M],s[M],st[M];
void Sol(ll x,ll mul) {
	if(x<st[1]) {s[x]+=mul;return;}
	int l=1,r=n,y;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(st[mid]<=x) y=mid,l=mid+1;
		else r=mid-1;
	}
	f[y]+=mul*(x/st[y]);x=x%st[y];
	if(x) Sol(x,mul);
}
int main() {
	scanf("%d%d",&n,&m);
	st[++top]=n;
	for(int i=1;i<=m;i++) {
		ll x;scanf("%lld",&x);
		while(x<=st[top]&&top) --top;
		st[++top]=x;
	}
	m=n;n=top;f[n]=1;
	for(int i=n-1;i>=1;i--) {
		f[i]+=f[i+1]*(st[i+1]/st[i]);
		Sol(st[i+1]%st[i],f[i+1]);
	}
	for(int i=st[1];i>=1;i--) s[i]+=s[i+1];
	for(int i=1;i<=st[1];i++) s[i]+=f[1];
	for(int i=1;i<=m;i++) printf("%lld\n",s[i]);
	return 0;
}