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 LL long long

const int maxn=1e5+10;

int n,m;
LL a1,a[maxn],t[maxn],suf[maxn];

int main()
{
#ifdef h10
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	int i;
	LL k,x;
	scanf("%lld%d",&a[1],&n);
	a1=a[1];
	m=1;
	for (i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		while (m&&x<=a[m]) m--;
		a[++m]=x;
	}
	n=m;

	t[n]=1;
	for (i=n;i>1;i--)
	{
		k=a[i];
		while (k>=a[1])
		{
			int l=1,r=i-1,mid;
			while (l<=r)
			{
				mid=(l+r)>>1;
				if (a[mid]<=k)
					l=mid+1;
				else
					r=mid-1;
			}
			t[r]+=t[i]*(k/a[r]);
			k%=a[r];
		}
		suf[k]+=t[i];
	}
	suf[a[1]]+=t[1];

	for (i=a1;i>=1;i--)
		suf[i]+=suf[i+1];
	for (i=1;i<=a1;i++)
		printf("%lld\n",suf[i]);

}