# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
constexpr int N=5e4;
constexpr ll INF=9e18;
int minn[200010],hmn[20][200010];
ll ans[100010];
bool vis[20][200010];
inline ll sq(ll x){return x*x;}
inline ll pw4(ll x){return sq(x)*sq(x);}
inline void chkmin(ll &x,const ll &y){x=(x<y?x:y);}
struct Func
{
	ll a,b;
	Func(){}
	Func(ll a,ll b):a(a),b(b){}
	ll operator()(ll x)const{return pw4(x-a)+b;}
}F[200010];
struct Update
{
	int l,r;
	Update(){}
	Update(int l,int r):l(l),r(r){}
}upd[200010];
struct Query
{
	int t,x;
	Query(){}
	Query(int t,int x):t(t),x(x){}
}qry[100010];
void update(int rt,int l,int r,int i,bool *vis,int *hmn)
{
	if(!vis[rt]) hmn[rt]=minn[rt],vis[rt]=1;
	if(!minn[rt]) return minn[rt]=i,void();
	if(l==r)
	{
		if(F[i](l)<F[minn[rt]](l)) minn[rt]=i;
		return;
	}
	int mid=(l+r)/2;
	if(F[i](mid)<F[minn[rt]](mid)) swap(i,minn[rt]);
	if(F[i](l)<F[minn[rt]](l)) update(rt*2,l,mid,i,vis,hmn);
	else if(F[i](r)<F[minn[rt]](r)) update(rt*2+1,mid+1,r,i,vis,hmn);
}
ll query(int rt,int l,int r,int x)
{
	if(!minn[rt]) return INF;
	if(l==r) return F[minn[rt]](x);
	int mid=(l+r)/2;
	ll ans=F[minn[rt]](x);
	if(x<=mid) chkmin(ans,query(rt*2,l,mid,x));
	else chkmin(ans,query(rt*2+1,mid+1,r,x));
	return ans;
}
void undo(int rt,int l,int r,bool *vis,int *hmn)
{
	if(!vis[rt]) return;
	minn[rt]=hmn[rt];vis[rt]=0;
	if(l==r) return;
	int mid=(l+r)/2;
	undo(rt*2,l,mid,vis,hmn);
	undo(rt*2+1,mid+1,r,vis,hmn);
}
void slv(int d,int l,int r,const vi &U,const vi &Q)
{
	if(l==r)
	{
		for(int i:U) update(1,1,N,i,vis[d],hmn[d]);
		for(int i:Q) ans[i]=query(1,1,N,qry[i].x);
		undo(1,1,N,vis[d],hmn[d]);
		return;
	}
	vi Ul,Ur,Ql,Qr;
	int mid=(l+r)/2;
	for(int i:U)
		if(l>=upd[i].l && r<=upd[i].r) update(1,1,N,i,vis[d],hmn[d]);
		else
		{
			if(mid>=upd[i].l) Ul.push_back(i);
			if(mid<upd[i].r) Ur.push_back(i);
		}
	for(int i:Q)
		if(qry[i].t<=mid) Ql.push_back(i);
		else Qr.push_back(i);
	slv(d+1,l,mid,Ul,Ql);
	slv(d+1,mid+1,r,Ur,Qr);
	undo(1,1,N,vis[d],hmn[d]);
}
int main()
{
	int T,n,m,op,t,x;
	ll a,b;
	cin>>T;
	while(T--)
	{
		int q=0;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%lld%lld",&F[i].a,&F[i].b),upd[i]=Update(1,m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%lld%lld",&a,&b);
				F[++n]=Func(a,b);
				upd[n]=Update(i,m);
			}
			else if(op==2) scanf("%d",&t),upd[t].r=i;
			else scanf("%d",&x),qry[++q]=Query(i,x);
		}
		vi U(n),Q(q);
		iota(U.begin(),U.end(),1);
		iota(Q.begin(),Q.end(),1);
		slv(0,1,m,U,Q);
		for(int i=1;i<=q;i++)
			if(ans[i]<INF) printf("%lld\n",ans[i]);
			else puts("-1");
	}
	return 0;
}