#include<bits/stdc++.h>
using namespace std;
int n,m;
int L[200100],R[201000];
#define ll long long
#define fi first
#define se second
ll a[200010],b[201000],ans[101000],X[100100];
#define pi pair<ll,ll>
#define pb push_back
vector<pi>g[400100],g2[401000];
void up(int p,int l,int r,int x,int y,int z){
    if(x<=l&&r<=y){g[p].pb({a[z],b[z]});return;}
    int mi=(l+r)>>1;
    if(x<=mi)up(p<<1,l,mi,x,y,z);
    if(y>mi)up(p<<1|1,mi+1,r,x,y,z);
}
void up2(int p,int l,int r,int x){
    g2[p].pb({X[x],1ll*x});if(l==r)return;int mi=(l+r)>>1;
    if(x<=mi)up2(p<<1,l,mi,x);
    else up2(p<<1|1,mi+1,r,x);
}
ll p4(ll x){
    return x*x*x*x;
}
const ll INF=4e18;
ll F(pi a,ll x){
    return p4(a.fi-x)+a.se;
}
void cdq(int pl,int pr,int l,int r,vector<pi>&a,vector<pi>&b){
    if(pl>pr||l>r)return;
    int mi=(l+r)>>1,jr=-1;ll nf=INF;
    //assert(a[pl].fi<=b[mi].fi);
    //assert(a[pl].fi<=b[l].fi);
    for(int i=pl;i<=pr;i++){
        if(a[i].fi>b[mi].fi)break;
        ll fe=F(a[i],b[mi].fi);
        assert(fe<INF);
        if(nf>fe)nf=fe,jr=i;
    }
    ans[b[mi].se]=min(ans[b[mi].se],nf);
    cdq(pl,jr,l,mi-1,a,b),cdq(jr,pr,mi+1,r,a,b);
}
void sol(vector<pi>&a,vector<pi>&b){
    sort(a.begin(),a.end());sort(b.begin(),b.end());
    int z=0;while(z<b.size()&&b[z].fi<a[0].fi)z++;
    if(z==b.size())return;
    assert(b[z].fi>=a[0].fi);
    for(int i=0;i+1<b.size();i++)
    assert(b[i].fi<=b[i+1].fi);
    for(int i=0;i+1<a.size();i++)
    assert(a[i].fi<=a[i+1].fi);
    cdq(0,a.size()-1,z,b.size()-1,a,b);
}
void sol(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]),L[i]=1,R[i]=m;
    for(int i=1;i<=m*4;i++)g[i].clear(),g2[i].clear();
    for(int i=1,op;i<=m;i++){
        scanf("%d",&op);
        X[i]=0;
        if(op==1){n++;scanf("%lld%lld",&a[n],&b[n]);L[n]=i,R[n]=m;}
        if(op==2){int x;scanf("%d",&x);R[x]=i;}
        if(op==3)scanf("%lld",&X[i]),up2(1,1,m,i),ans[i]=INF;
    }
    for(int i=1;i<=n;i++)up(1,1,m,L[i],R[i],i);
    for(int p=1;p<=m*4;p++)if(!g[p].empty()&&!g2[p].empty()){
        sol(g[p],g2[p]);
        for(pi &a:g[p])a.fi=-a.fi;
        for(pi &b:g2[p])b.fi=-b.fi;
        sol(g[p],g2[p]);
    }
    for(int i=1;i<=m;i++)if(X[i]){
        if(ans[i]==INF)puts("-1");
        else printf("%lld\n",ans[i]);
    }
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}