#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];
#define pi pair<ll,ll>
#define pb push_back
vector<pi>g[400100],g2[401000];
ll X[100100];
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);
}
const int V=5e4;
int kl,kr;
pi sta[100100];
ll p4(ll x){
    return x*x*x*x;
}
ll F(pi a,ll x){
    return p4(a.fi-x)+a.se;
}
void sol(vector<pi>a,vector<pi>b){
    sort(a.begin(),a.end());sort(b.begin(),b.end());
    int as=a.size(),i=0;
    kl=kr=0;
    for(pi t:b){
        while(i<as&&a[i].fi<=t.fi){
            if(!kr)L[1]=a[i].fi,R[1]=V,sta[1]=a[i],kl=kr=1;
            else{
                while(R[kl]<a[i].fi)kl++;L[kl]=a[i].fi;
                if(F(sta[kr],V)<=F(a[i],V))continue;
                while(kl<=kr&&F(sta[kr],L[kr])>=F(a[i],L[kr]))kr--;
                if(kl<=kr){
                    ll l=L[kr],r=R[kr];
                    while(l<=r){
                        ll mi=(l+r)>>1;
                        if(F(sta[kr],mi)>=F(a[i],mi))R[kr]=r=mi-1;
                        else l=mi+1;
                    }
                }
                sta[++kr]=a[i];
                if(kl==kr)L[kr]=a[i].fi;else L[kr]=R[kr-1]+1;
                R[kr]=V;
            }
            i++;
        }
        if(!kr)continue;
        while(R[kl]<t.fi)kl++;L[kl]=t.fi;
        ans[t.se]=min(ans[t.se],F(sta[kl],t.fi));
    }
}
const ll INF=4e18;
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=V+1-a.fi;
        for(pi &b:g2[p])b.fi=V+1-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;
}