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>
#include<set>
using namespace std;
#define ll long long
ll read()
{
	ll x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 100000
ll q[MN+5],ans[MN+5];
multiset< pair<ll,ll> > st;
int main()
{
	int n,i;ll s;
	set< pair<ll,ll> >::iterator it,tt;
	q[0]=read();n=read();
	for(i=1;i<=n;++i)q[i]=read();
	st.insert(make_pair(q[n],1));
	for(i=n;i--;)
	{
		for(s=0,it=st.end(),--it;it->first>q[i];)
		{
			s+=it->first/q[i]*it->second;
			st.insert(make_pair(it->first%q[i],it->second));
			tt=it;--it;st.erase(tt);
		}
		st.insert(make_pair(q[i],s));
	}
	for(it=st.begin();it!=st.end();++it)ans[it->first]+=it->second;
	for(i=q[0];--i;)ans[i]+=ans[i+1];
	for(i=1;i<=q[0];++i)printf("%lld\n",ans[i]);
}