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;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> a(m);
  for(Int i=0;i<m;i++) cin>>a[i];
  a.emplace(a.begin(),n);
  stack<Int> b;
  for(Int i=0;i<(Int)a.size();i++){
    while(!b.empty()&&b.top()>=a[i]) b.pop();
    if(b.empty()||b.top()<a[i]) b.emplace(a[i]);
  }
  m=b.size();
  a.resize(m);
  for(Int i=0;i<m;i++){
    a[i]=b.top();b.pop();
  }

  vector<Int> t(m,0),ans(n+1,0);
  t[0]=1;
  for(Int i=0;i<m;i++){
    Int k=a[i];
    Int j=i;
    while(1){
      Int l=j,r=m;
      while(l+1<r){
	Int p=(l+r)>>1;
	if(k>=a[p]) r=p;
	else l=p;
      }
      if(r==m) break;
      j=r;
      t[j]+=t[i]*(k/a[j]);
      k%=a[j];
    }
    ans[0]+=t[i];
    ans[k]-=t[i];
  }
  
  for(Int i=1;i<n;i++) ans[i]+=ans[i-1];
  for(Int i=0;i<n;i++) cout<<ans[i]<<endl;
  
  return 0;
}