在加强版中测试过了，最慢点616ms.

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,ans,cnt,root;
double sqr(double x){return x*x; }
struct Query{int x,y;}q[1000010];
struct Point {int x,y,del,rev;}a[1000010];
int lc[1000010],rc[1000010],d[1000010];
int L[1000010],R[1000010],D[1000010],U[1000010];
int id[1000010];
void calc(int x,int y)
{
	L[x]=min(L[x],L[y]),D[x]=min(D[x],D[y]);
	R[x]=max(R[x],R[y]),U[x]=max(U[x],U[y]);
}
void pushup(int x)
{
	if(!a[x].del)L[x]=R[x]=a[x].x,D[x]=U[x]=a[x].y;
	else L[x]=D[x]=INF,R[x]=U[x]=-1;
	if(lc[x])calc(x,lc[x]);
	if(rc[x])calc(x,rc[x]);
}
int build(int l, int r)
{
	if(l>r)return 0;
	int mid=l+r>>1;
	int mxx=-1e9,mnx=1e9,mxy=-1e9,mny=1e9;
	for(int i=l;i<=r;i++)
	mxx=max(mxx,a[i].x),mnx=min(mnx,a[i].x),
	mxy=max(mxy,a[i].y),mny=min(mny,a[i].y);
	if(mxx-mnx>mxy-mny)
	nth_element(a+l,a+mid,a+r+1,[&](Point u,Point v){return u.x<v.x;}),d[mid]=1;
	else
	nth_element(a+l,a+mid,a+r+1,[&](Point u,Point v){return u.y<v.y;}),d[mid]=2;
	id[a[mid].rev]=mid;
	lc[mid]=build(l,mid-1);
	rc[mid]=build(mid+1,r);
	pushup(mid);
	return mid;
}
void update(int l,int r,int x)
{
	int mid=l+r>>1;
	if(x==mid)return a[x].del=0,pushup(x),void();
	if(x<mid)update(l,mid-1,x);else update(mid+1,r,x);
	pushup(mid);
}
Point k;
int dis(Point u,Point v){return abs(u.x-v.x)+abs(u.y-v.y);}
int mndis(int u,Point v)
{
	if(!u)return INF;
	int s=0;
	if(v.x<L[u])s+=L[u]-v.x;
	if(v.x>R[u])s+=v.x-R[u];
	if(v.y<D[u])s+=D[u]-v.y;
	if(v.y>U[u])s+=v.y-U[u];
	return s;
}
void query(int x) 
{
	if(!a[x].del)ans=min(ans,dis(a[x],k));
	int dl=mndis(lc[x],k),dr=mndis(rc[x],k);
	if(dl<ans&&dr<ans){
		if(dl<dr){
			query(lc[x]);
			if(dr<ans)query(rc[x]);
		}
		else{
			query(rc[x]);
			if(dl<ans)query(lc[x]);
		}
	}
	else{
		if(dl<ans)query(lc[x]);
		if(dr<ans)query(rc[x]);
	}
}
int T[1000010];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int i;
	cin>>n>>m;
	cnt=n;
	for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y,a[i].rev=i;
	for(i=1;i<=m;i++){
		int t,x,y;
		cin>>t>>x>>y;
		if(t==1) 
        a[++cnt]={x,y,1,cnt};else q[i]={x,y};
		T[i]=t;
	}
	root=build(1,cnt);
	int t=n;
	for(i=1;i<=m;i++) 
		if(T[i]==1)update(1,cnt,id[++t]);
		else{
			ans=INF,k={q[i].x,q[i].y};
			query(root);
			cout<<ans<<'\n';
		}
}