#include<bits/stdc++.h>
#define int long long
#define MAXN 500010
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int tst,typ,n,ans[MAXN];
int id[MAXN],unq[MAXN],N;
struct qnode{int l,r,id;}que[MAXN];
struct BIT{
	int t[MAXN];
	int lowbit(int x){return x&(-x);}
	void update(int x,int y){for(;x<N;x+=lowbit(x))t[x]+=y;}
	int query(int x){int ret=0;for(;x;x-=lowbit(x))ret+=t[x];return ret;}
	void clear(){for(int i=1;i<=N;i++)t[i]=0;}
}T;
struct Segtree{
	int t[MAXN<<2],id[MAXN<<2],tag[MAXN<<2];
	void pushup(int p){t[p]=min(t[p<<1],t[p<<1|1]);id[p]=min(t[p<<1]==t[p]?id[p<<1]:inf,t[p<<1|1]==t[p]?id[p<<1|1]:inf);}
	void add(int p,int d){t[p]+=d;tag[p]+=d;}
	void pushdown(int p){
		if(!tag[p])return;
		add(p<<1,tag[p]);add(p<<1|1,tag[p]);
		tag[p]=0;
	}
	void build(int p,int l,int r){
		t[p]=inf;id[p]=tag[p]=0;if(l==r)return;
		int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	}
	void update(int p,int l,int r,int pos,int v,int d){
		if(l==r)return (void)(t[p]=v,id[p]=d);
		int mid=(l+r)>>1;pushdown(p);
		if(pos<=mid)update(p<<1,l,mid,pos,v,d);
		else update(p<<1|1,mid+1,r,pos,v,d);
		pushup(p);
	}
	void add(int p,int l,int r,int L,int R,int d){
		if(L>R)return;if(L<=l&&r<=R)return add(p,d);
		int mid=(l+r)>>1;pushdown(p);
		if(L<=mid)add(p<<1,l,mid,L,R,d);
		if(R>mid)add(p<<1|1,mid+1,r,L,R,d);
		pushup(p);
	}
	pii query(int p,int l,int r,int L,int R){
		if(L>R)return mp(inf,0);if(L<=l&&r<=R)return mp(t[p],id[p]);
		int mid=(l+r)>>1;pushdown(p);
		if(R<=mid)return query(p<<1,l,mid,L,R);
		if(L>mid)return query(p<<1|1,mid+1,r,L,R);
		return min(query(p<<1,l,mid,L,R),query(p<<1|1,mid+1,r,L,R));
	}
}T1,T2;
set<pii>ql,qr;
int f[MAXN];
int get(int x){return f[x]==x?x:f[x]=get(f[x]);}
signed main(){
	scanf("%lld%lld",&tst,&typ);
	while(tst--){
		scanf("%lld",&n);ql.clear();qr.clear();N=0;
		for(int i=1;i<=n;i++)scanf("%lld%lld",&que[i].l,&que[i].r),que[i].id=i,unq[++N]=que[i].l,unq[++N]=que[i].r;
		sort(que+1,que+n+1,[&](qnode a,qnode b){return a.r==b.r?a.id<b.id:a.r<b.r;});
		sort(unq+1,unq+N+1);N=unique(unq+1,unq+N+1)-unq-1;
		for(int i=1;i<=n;i++){
			que[i].l=lower_bound(unq+1,unq+N+1,que[i].l)-unq;
			que[i].r=lower_bound(unq+1,unq+N+1,que[i].r)-unq;
			id[que[i].id]=i;
		}
		T.clear();
		for(int i=1;i<=N;i++)f[i]=i;
		T1.build(1,1,n);T2.build(1,1,n);
		for(int i=1;i<N;i++)T.update(i,unq[i+1]-unq[i]);
		for(int i=1;i<=n;i++)T2.update(1,1,n,i,-que[i].l,i);
		for(int r=n+1;r>1;){
			int pos=T2.query(1,1,n,1,r-1).se;T2.update(1,1,n,pos,inf,0);
			T1.update(1,1,n,pos,T.query(que[pos].r-1)-T.query(que[pos].l-1),que[pos].id);
			ql.insert(mp(que[pos].l,pos));qr.insert(mp(que[pos].r,pos));r=pos;//cerr<<"add:"<<pos<<' '<<que[pos].id<<' '<<T.query(que[pos].r-1)-T.query(que[pos].l-1)<<endl;
		}
		ql.insert(mp(0,0));ql.insert(mp(N,n+1));
		qr.insert(mp(0,0));qr.insert(mp(N,n+1));
		for(int i=1;i<=n;i++){
			int pos=id[T1.id[1]];ans[i]=que[pos].id;//cerr<<"solve:"<<i<<' '<<pos<<' '<<que[pos].id<<' '<<T1.t[1]<<endl;
			T1.update(1,1,n,pos,inf,0);
			for(int j=get(que[pos].l);j<que[pos].r;j=get(j)){
				int l=qr.lower_bound(mp(j,inf))->se,r=(--ql.lower_bound(mp(j,inf)))->se;
				T1.add(1,1,n,l,r,unq[j]-unq[j+1]);T.update(j,unq[j]-unq[j+1]);
				f[j]=j+1;
			}
			int l=(--ql.find(mp(que[pos].l,pos)))->se,r=(++ql.find(mp(que[pos].l,pos)))->se;
			ql.erase(mp(que[pos].l,pos));qr.erase(mp(que[pos].r,pos));
			while(r>1){
				int np=T2.query(1,1,n,1,r-1).se;
				if(np<=l||que[np].l<=que[l].l)break;
				T2.update(1,1,n,np,inf,0);T1.update(1,1,n,np,T.query(que[np].r-1)-T.query(que[np].l-1),que[np].id);
				ql.insert(mp(que[np].l,np));qr.insert(mp(que[np].r,np));r=np;//cerr<<"add:"<<np<<' '<<que[np].id<<' '<<T.query(que[np].r-1)-T.query(que[np].l-1)<<endl;
			}
		}
		for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
		puts("");
	}
	return 0;
}