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 <cstring>
#include <map> 
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e5 + 500;

vector < ll > q;
map < ll, ll > S;
ll sol[N];
int n, Q;

int main(){
	scanf("%d%d", &n, &Q);
	q.PB(n);
	for(int i = 0;i < Q;i++){
		ll x; scanf("%lld", &x);
		while((int)q.size() > 0 && q.back() >= x)
			q.pop_back();
		q.PB(x);
	}
	Q = (int)q.size();
	S[q[Q - 1]] = 1;
	for(int i = Q - 2;i >= 0;i--){
		while(S.rbegin() -> X > q[i]){
			S[q[i]] += S.rbegin() -> Y * (S.rbegin() -> X / q[i]);
			S[S.rbegin() -> X % q[i]] += S.rbegin() -> Y;
			S.erase(--S.end()); 
		}
	}
	for(int i = n;i >= 1;i--){
		sol[i] = sol[i + 1] + S[i];
	}
	for(int i = 1;i <= n;i++)
		printf("%lld\n", sol[i]);
	return 0;
}