給定兩個正整數\(n,q\)和\(n\)個正整數\(a_1,a_2,...,a_n\)。

你必須做以下操作\(q\)次：

如果目前\(a_1,a_2,...,a_n\)都是零，則輸出\(0\)。

否則令\(x\)是目前\(a_1,a_2,...,a_n\)中最小的非零整數。

接下來輸出\(x\)。

然後把\(a_1,a_2,...,a_n\)所有非零的整數都減掉\(x\)。

Input

第一行輸入兩個正整數\(n,q\)。

第二行輸入\(n\)個正整數\(a_1,a_2,...,a_n\)。

\(1\le n,q\le 10^{5},1\le a_i\le10^9\)

Output

輸出\(q\)行，其中第\(i\)行輸出的整數代表第\(i\)次操作的輸出。

Constraints

第 \(1\) 組測資 \(10\) 分：\(n,q\le 1000\)。

第 \(2\) 組測資 \(20\) 分：\(n\le 5000\)。

第 \(3\) 組測資 \(70\) 分：無特別限制。

Sample Input 1

3 5
1 2 3

Sample Output 1

1
1
1
0
0

Sample Input 2

4 2
10 3 5 3

Sample Output 2

3
2