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 N 100005
#define LL long long
#define mod 1000000007
#define pr pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;

LL read(){
	char c=getchar();
	LL t=0,f=1;
	while(c>'9'||c<'0') f=(c=='-')?-1:1,c=getchar();
	while(c>='0'&&c<='9') t=t*10+c-'0',c=getchar();
	return t*f;
}

int n,Q;
LL a[N],dt[N],t[N],now,tp;

int find(LL v,int lim){
	int l=0,r=lim,mid,ret=0;
	while(l<=r) (a[mid=(l+r)>>1]<=v)?(ret=mid,l=mid+1):(r=mid-1);
	return ret;
}

int main(){
	n=read(),Q=read(),a[++tp]=n;
	for(int i=1;i<=Q;i++){
		LL x=read();
		while(x<=a[tp]) tp--;
		a[++tp]=x; 
	}
	t[tp]=1;
	for(int i=tp;i;i--){
		LL res=a[i],po=find(res,i-1);
		for(;po;po=find(res,po-1)) t[po]+=(res/a[po])*t[i],res%=a[po];
		dt[1]+=t[i],dt[res+1]-=t[i];
	}
	for(int i=1;i<=n;i++) printf("%lld\n",(now+=dt[i]));
}