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<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int n,m,p;
long long x[100010],f[100010],s[100010];
int main()
{
	//freopen("sequence.in","r",stdin);
	//freopen("sequence.out","w",stdout);
	int i,j;
	long long k;
	scanf("%d%d",&n,&m);
	p=1;
	x[1]=n;
	while(m--)
	  {
       scanf("%lld",&k);
       while(x[p]>=k)
         p--;
       x[++p]=k;
      }
    f[p]=1;
    for(i=p;i>0;i--)
      {
       k=x[i];
       while(1)
         {
          j=upper_bound(x+1,x+i,k)-x-1;
          if(!j)
            break;
          f[j]+=k/x[j]*f[i];
          k%=x[j];
         }
       s[k]+=f[i];
      }
    for(i=n;i>0;i--)
      s[i]+=s[i+1];
    for(i=1;i<=n;i++)
      printf("%lld\n",s[i]);
	return 0;
}