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;
#define int long long
const int maxn=1000001;
int n,l,t,x,w,m,ans[maxn],len[maxn],q,c[maxn];
void work(int x,int val)
{
	if(!x)return;
	int pos=upper_bound(len+1,len+m,x)-len-1;
	if(pos==0)c[1]+=val,c[x+1]-=val;
	else ans[pos]+=(x/len[pos])*val,work(x%len[pos],val);
}
signed main()
{
    cin>>n>>q;
    len[++m]=n;
    for(int i=1;i<=q;i++)
    {
    	cin>>x;
    	while(m&&len[m]>=x)m--;	
    	len[++m]=x;
	}
	ans[m]=1;
	for(int i=m;i>=2;i--)
	{
		ans[i-1]+=ans[i]*(len[i]/len[i-1]);
		work(len[i]%len[i-1],ans[i]);
	}
    c[1]+=ans[1],c[len[1]+1]-=ans[1];
    for(int i=1;i<=n;i++)c[i]+=c[i-1],cout<<c[i]<<" ";
    
}
/*
首先排掉没有用的操作，最后就单调增。
对于当前操作x，首先len[x]/len[x-1]下取整*len[x-1]这一段肯定是直接转移的
剩下len[x]%len[x-1]这一段可以二分跳出来。
发现向后转移和倒着扫这件事情非常矛盾，
所以直接转移的部分考虑用数组记录一下，出现的次数。
 

 
 
 
 
*/