1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<cstring>  5 #include<queue>  6 using namespace std;  7 const int INF=1e9;  8 const int mxn=500010;  9 int read(){ 10     int x=0,f=1;char ch=getchar(); 11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();} 13     return x*f; 14 } 15 struct node{ 16     int max[2],min[2]; 17     int d[2]; 18     int l,r; 19 }t[mxn<<2]; 20 int nowD=0; 21 int cmp(const node a,const node b){ 22     return ((a.d[nowD]<b.d[nowD]) || (a.d[nowD]==b.d[nowD] && a.d[!nowD]<b.d[!nowD])); 23 } 24 int root,nct=0; 25 int n,m; 26 void pushup(int rt,int x){ 27     t[rt].max[0]=max(t[rt].max[0],t[x].max[0]); 28     t[rt].min[0]=min(t[rt].min[0],t[x].min[0]); 29     t[rt].max[1]=max(t[rt].max[1],t[x].max[1]); 30     t[rt].min[1]=min(t[rt].min[1],t[x].min[1]); 31     return; 32 } 33 int Build(int l,int r,int D){ 34     int mid=(l+r)>>1; 35     nowD=D; 36     nth_element(t+l,t+mid,t+r+1,cmp); 37     t[mid].max[0]=t[mid].min[0]=t[mid].d[0]; 38     t[mid].max[1]=t[mid].min[1]=t[mid].d[1]; 39     if(l!=mid){t[mid].l=Build(l,mid-1,D^1);}  40     if(r!=mid){t[mid].r=Build(mid+1,r,D^1);} 41     if(t[mid].l)pushup(mid,t[mid].l); 42     if(t[mid].r)pushup(mid,t[mid].r); 43     return mid; 44 } 45 void insert(int x){ 46     int now=root,D=0; 47     while(1){ 48         pushup(now,x); 49         if(t[x].d[D]>=t[now].d[D]){ 50             if(!t[now].r){t[now].r=x;return;} 51             else now=t[now].r; 52         } 53         else{ 54             if(!t[now].l){t[now].l=x;return;}  55             else now=t[now].l; 56         }  57         D^=1; 58     } 59     return; 60 } 61 int qx,qy,ans; 62 int Dist(int k){ 63     int res=0; 64     if(qx>t[k].max[0])res+=qx-t[k].max[0]; 65     if(qx<t[k].min[0])res+=t[k].min[0]-qx; 66     if(qy>t[k].max[1])res+=qy-t[k].max[1]; 67     if(qy<t[k].min[1])res+=t[k].min[1]-qy; 68     return res; 69 } 70 void query(int rt){ 71     int dx,dy,tmp; 72     tmp=abs(qx-t[rt].d[0])+abs(qy-t[rt].d[1]); 73     if(tmp<ans)ans=tmp; 74     if(t[rt].l) dx=Dist(t[rt].l);else dx=INF; 75     if(t[rt].r) dy=Dist(t[rt].r);else dy=INF; 76     if(dx<dy){ 77         if(dx<ans) query(t[rt].l); 78         if(dy<ans) query(t[rt].r); 79     } 80     else{ 81         if(dy<ans) query(t[rt].r); 82         if(dx<ans) query(t[rt].l); 83     } 84     return; 85 } 86 int main(){ 87     int i,j; 88     n=read();m=read(); 89     int c,x,y; 90     for(i=1;i<=n;i++){t[++nct].d[0]=read();t[nct].d[1]=read();} 91     root=Build(1,nct,0); 92     while(m--){ 93         c=read();x=read();y=read(); 94         if(c==1){ 95             t[++nct].d[0]=x;t[nct].d[1]=y; 96             t[nct].max[0]=t[nct].min[0]=x; 97             t[nct].max[1]=t[nct].min[1]=y; 98             insert(nct); 99         }100         else{101             qx=x;qy=y;ans=INF;102             query(root);103             printf("%d\n",ans);104         }105     }106     return 0;107 }108