#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 210000;
const int maxv = 50000;
const int inf  = LLONG_MAX;

int n,m;
struct node
{
	int a,b;
}ai[maxn];
int li[maxn],ri[maxn];
int qV[maxn],qi[maxn];
int ans[maxn],ansn;

int calc(int x,int a,int b) 
{
	int k=x-a,kk=k*k;
	return kk*kk+b;
}
struct lichaoseg
{
	int sa[(maxv+5)<<2],sb[(maxv+5)<<2];
	void build(const int x,const int l,const int r)
	{
		sa[x]=sb[x]=0;
		if(l==r) return;
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		build(lc,l,mid); build(rc,mid+1,r);
	}
	int ca,cb;
	void add(const int x,const int l,const int r,vector< pair<int*,int> >&V)
	{
		if(sa[x]==0)
		{
			V.emplace_back( &sa[x],sa[x] );
			V.emplace_back( &sb[x],sb[x] );
			sa[x]=ca;
			sb[x]=cb;
			return;
		}
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		
		int l0=calc(l,sa[x],sb[x]),r0=calc(r,sa[x],sb[x]);
		int l1=calc(l,ca,cb),r1=calc(r,ca,cb);
		if(l0<=l1 && r0<=r1) return;
		if(l0>=l1 && r0>=r1)
		{
			V.emplace_back( &sa[x],sa[x] );
			V.emplace_back( &sb[x],sb[x] );
			sa[x]=ca;
			sb[x]=cb;
			return;
		}
		
		int m0=calc(mid,sa[x],sb[x]),m1=calc(mid,ca,cb);
		if(l0<=l1)
		{
			if(m0<=m1) add(rc,mid+1,r,V);
			else
			{
				V.emplace_back( &sa[x],sa[x] );
				V.emplace_back( &sb[x],sb[x] );
				swap(sa[x],ca);
				swap(sb[x],cb);
				add(lc,l,mid,V);
			}
		}
		else
		{
			if(m0<=m1) add(lc,l,mid,V);
			else
			{
				V.emplace_back( &sa[x],sa[x] );
				V.emplace_back( &sb[x],sb[x] );
				swap(sa[x],ca);
				swap(sb[x],cb);
				add(rc,mid+1,r,V);
			}
		}
	}
	int loc;
	int query(const int x,const int l,const int r)
	{
		int ret=inf;
		if(sa[x]) ret=min(ret,calc(loc,sa[x],sb[x]));
		
		if(l==r) return ret;
		
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		if(loc<=mid) ret=min(ret,query(lc,l,mid));
		else ret=min(ret,query(rc,mid+1,r));
		return ret;
	}
}segl;
struct segment
{
	vector<int>segV[maxn<<2];
	int sum[maxn<<2];
	void build(const int x,const int l,const int r)
	{
		vector<int>_; segV[x].swap(_);
		if(l==r)
		{
			sum[x]= qV[l]>0;
			return;
		}
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		build(lc,l,mid); build(rc,mid+1,r);
		sum[x]=sum[lc]+sum[rc];
	}
	int lx,rx,c;
	void add(const int x,const int l,const int r)
	{
		if(rx<l||r<lx) return;
		if(lx<=l&&r<=rx)
		{
			segV[x].push_back(c);
			return;
		}
		int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
		add(lc,l,mid); add(rc,mid+1,r);
	}
	void query(const int x,const int l,const int r)
	{
		if(!sum[x]) return;
		
		//do
		vector< pair<int*,int> >V;
		for(auto i:segV[x])
		{
			segl.ca=ai[i].a,segl.cb=ai[i].b;
			segl.add(1,1,maxv,V);
		}
		
		if(l==r)
		{
			int k=qV[l];
			segl.loc=qi[k];
			ans[k]= segl.query(1,1,maxv);
		}
		else
		{
			int mid=(l+r)>>1,lc=x<<1,rc=lc|1;
			query(lc,l,mid); query(rc,mid+1,r);
		}
		
		//undo
		for(int i=V.size()-1;i>=0;i--)
		{
			(*V[i].first)=V[i].second;
		}
	}
}segt;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) 
		{
			cin>>ai[i].a>>ai[i].b;
			li[i]=1; ri[i]=-1;
		}
		
		for(int i=1;i<=m;i++) qV[i]=0;
		
		ansn=0;
		for(int i=1;i<=m;i++)
		{
			int op; cin>>op;
			qV[i]=0;
			if(op==1)
			{
				n++;
				cin>>ai[n].a>>ai[n].b;
				li[n]=i; ri[n]=-1;
			}
			else if(op==2)
			{
				int x; cin>>x;
				ri[x]=i-1;
			}
			else
			{
				int x; cin>>x;
				qV[i]=++ansn;
				qi[ansn]=x;
			}
		}
		for(int i=1;i<=n;i++) if(ri[i]==-1)
			ri[i]=m;
		
		segl.build(1,1,maxv);
		segt.build(1,1,m);
		for(int i=1;i<=n;i++) if(li[i]<=ri[i])
		{
			segt.lx=li[i],segt.rx=ri[i],segt.c=i;
			segt.add(1,1,m);
		}
		segt.query(1,1,m);
		
		for(int i=1;i<=ansn;i++) 
		{
			if(ans[i]==inf) ans[i]=-1;
			cout<<ans[i]<<'\n';
		}
	}
	
	return 0;
}