Description

泽渡真琴有一个长度为 $n$ 的序列 $c$，初始 $c_i=0$。

现在相泽祐一对 $c$ 做了 $m$ 次操作。第 $i$ 次操作任意地选出 $a_i$​ 个不同的位置，并将这些位置上的值 $+1$。

显然最终 $c$ 的形态是不定的。真琴想知道在所有可能的序列中，值恰好为 k 的位置最多有多少个。对 $k\in[1,m]$ 都求出答案。

Format

Input

第一行两个整数 $n, m$。

接下来一行 $m$ 个数 $a_1, a_2, \cdots , a_m$。

Output

一行 $m$ 个数，分别表示 $k = 1, 2, \cdots , m$ 时候的答案。

Samples

3 3
1 2 3

1 3 1

6 6
2 2 3 3 4 4

3 4 6 4 3 2

Limitation

对于 $20\%$ 的数据，$1\le n, m \le 10$。

对于 $55\%$ 的数据，$1\le n, m \le 5000$ 且 $1\le a_i\le 2$。

对于 $70\%$ 的数据，$1\le n, m \le 5000$。

对于 $100\%$ 的数据，$1\le n, m \le 2 \times 10^5 , 1 \le a_i \le n$。