B. Ehab and subtraction

You're given an array aa. You should repeat the following operation kk times: find the minimum non-zero element in the array, print it, and then subtract it from all the non-zero elements of the array. If all the elements are 0s, just print 0.

Input

The first line contains integers nn and kk (1≤n,k≤105)(1≤n,k≤105), the length of the array and the number of operations you should perform.

The second line contains nn space-separated integers a1,a2,…,ana1,a2,…,an (1≤ai≤109)(1≤ai≤109), the elements of the array.

Output

Print the minimum non-zero element before each operation in a new line.

Examples

input

3 5
1 2 3

output

1
1
1
0
0

input

4 2
10 3 5 3

output

3
2

 

题目大意：给出n个元素的数字序列，进行k次操作，每次操作找出序列中最小的非零元素并输出，然后让序列中的所有非零元素都减去这个最小非零元素的值。如果序列中全为0，则输出0.

 

暴力解是行不通的，数据各种卡边界。我用的方法是对序列排序后，第一次找出最小的非零元素，使用maxn获取他的值用于输出，然后sum累加这个值，后面继续进行操作时，判断当前元素减去sum是否等于0，不等于0说明这个元素是当前序列的最小非零元素。

后台有个特殊数据：

由于这个序列只需要一次减值就全部为0，为了防止后续操作不停的找最小非零元素，用了一个fflag来标记序列是否全部为0，同时能让序列第一次归零时不输出0.

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)
 
int a[100005];
 
int main()
{
	int n,m,i,j,flag,maxn,sum,fflag;
	cin>>n>>m;
	for(i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	flag=0;                //当前进行操作的元素的下标位置
	maxn=0;
	sum=0;
	fflag=0;
	for(i=0;i<m;i++)
	{
		if(fflag)
		{
			cout<<"0"<<endl;
			continue;
		}		
		for(j=flag;j<n;j++)
		{
			if(a[j]-sum>0)
			{
				flag=j+1;
				maxn=a[j]-sum;
				sum+=maxn;
				cout<<maxn<<endl;
				break;
			}
		}
		if(a[n-1]==sum)
			fflag=1;	
	}
	return 0;
}