ll@q;
rep(q){
	ll@n,@m,@k,@p,@t[n],@c--[n],@b[m],@d--[m],@s[k],v[m];
	sortA_index(m,b,d,v);
	vector<ll>u[k];
	rep(j,m){
		u[d[j]].push_back(j);
	}
	ll zi=-1,zj=-1;
	ll a=0,r=2d9;
	while(a+1<r){
		ll e=a+r>>1;
		ll y=0;
		rep(i,n){
			ll f=bsearch_min[ll,j,0,m](t[i]+b[j]>=e);
			ll g=bsearch_min[ll,j,0,m](t[i]+b[j]-s[c[i]]>=e);
			y+=f;
			vector<ll>&w=u[c[i]];
			y-=bsearch_min[ll,x,0,w.size()](w[x]>=f);
			y+=bsearch_min[ll,x,0,w.size()](w[x]>=g);
		}
		(y<p?a:r)=e;
	}
	rep(i,n){
		ll j;
		j=bsearch_min[ll,j,0,m](t[i]+b[j]>=a);
		if(j<m&&t[i]+b[j]==a&&c[i]!=d[j]){
			zi=i;
			zj=j;
			goto done;
		}
		j=bsearch_min[ll,j,0,m](t[i]+b[j]>a)-1;
		if(j>=0&&t[i]+b[j]==a&&c[i]!=d[j]){
			zi=i;
			zj=j;
			goto done;
		}
		j=bsearch_min[ll,j,0,m](t[i]+b[j]-s[c[i]]>a||t[i]+b[j]-s[c[i]]==a&&d[j]>=c[i]);
		if(j<m&&t[i]+b[j]-s[c[i]]==a&&d[j]==c[i]){
			zi=i;
			zj=j;
			goto done;
		}
	}
	wt("nakatta");
	done:;
	wt(zi+1,v[zj]+1);
}