#include <cstdio>
const int M = 2000005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,d,tot,now,a[M],b[M],p[M],cnt[M];
struct node
{
	int x,id;
	node(int X=0,int I=0) : x(X) , id(I) {}
	bool operator < (const node &b) const
	{
		return x<b.x;
	}
}t[M],ans;
struct Q
{
	int l,r;
	Q(int x=1){l=x;r=x-1;}
	void push(node x)
	{
		while(l<=r && x<t[r]) r--;
		t[++r]=x;
	}
	void get()
	{
		while(l<=r && t[l].id<now) l++;
		if(l<=r && t[l]<ans) ans=t[l];
	}
}q[M];
int Abs(int x)
{
	return x>0?x:-x;
}
void add(int x)
{
	q[b[x+1]+n].push(node(a[x],x));
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=(read()?1:-1);
	for(int i=n;i>=1;i--)
		b[i]+=b[i+1],cnt[b[i+1]+n]++,tot+=!b[i];
	for(int i=0,s=1;i<=2*n;i++)
		q[i]=Q(s),s+=cnt[i];
	if(!b[1]) d=(tot<m);
	else d=(Abs(b[1])-1)/m+1;
	if(!d)
	{
		tot=0;now=1;
		for(int i=1;i<=n;i++)
			if(!b[i+1]) p[++tot]=i;
		for(int i=1,j=1;i<m;i++)
		{
			while(j<=tot && tot-j>=m-i)//make sure enough 0-position
				q[0].push(node(a[p[j]],p[j])),j++;
			ans.x=M;q[0].get();now=ans.id+1;
			printf("%d ",ans.x);
		}
	}
	else
	{
		int r=now=1;
		while(n-r>=m-1) add(r++);//vaild positions
		while(m>1)
		{
			int sd=b[now]+n;ans.x=M;
			for(int i=sd-d;i<=sd+d;i++)
				if(Abs(i-n)<=d*(m-1)) q[i].get();
			printf("%d ",ans.x);
			now=ans.id+1;add(r++);m--;
		}
	}
	printf("%d\n",a[n]);
}