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 N = 200000;
int n, q;
LL s[N], top;
LL f[N], g[N];
int main()
{
    cin >> n >> q;
    top = 1; s[1] = n;
    for (int i = 1; i <= q; ++ i)
    {
        LL x;
        cin >> x;
        while (s[top] >= x) s[top --] = 0;
        s[++ top] = x;
    }
    f[top] = 1;
    for (int i = top; i > 1; -- i)
    {
        LL x = s[i];
        while (x > s[1])
        {
            int t = lower_bound(s + 1, s + top + 1, x) - s - 1;
            f[t] += (x / s[t]) * f[i];
            x %= s[t];
        }
        g[x] += f[i];
        f[i] = 0;
    }
    g[s[1]] += f[1];
    for (int i = n; i >= 1; -- i) g[i] += g[i + 1];
    for (int i = 1; i <= n; ++ i) cout << g[i] << endl;
}