#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cctype>

 using namespace std;

 char c;void read(int &x){

     c=getchar();x=;int f=;

     while(!isdigit(c)) c=getchar(),f=(f&&c!='-');

     while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();

     x=f?x:-x;

 }

 void print(int x){

     if(x<) putchar('-'),x=-x;

     if(x>) print(x/);

     putchar(x%+);

 }

 inline int max(int a,int b){return a>b?a:b;}

 inline int min(int a,int b){return a<b?a:b;}

 inline int abs(int a){return a<?-a:a;}

 #define N 1000010

 #define alph (0.75)

 #define inf 1e9+7

 int n,m,rt,u,ans;

 int lit[N],tp1,tp2;

 int d;struct node{

     int p[];

     void init(){read(p[]);read(p[]);}

     bool operator < (const node &t) const{

         return p[d]<t.p[d];

     }

 }b[N];

 struct data{int mx[],my[],ch[],sz,fa;node ad;}a[N];

 #define lc a[o].ch[0]

 #define rc a[o].ch[1]

 inline void up(int o){

     a[o].mx[]=max(a[o].mx[],max(a[lc].mx[],a[rc].mx[]));

     a[o].mx[]=min(a[o].mx[],min(a[lc].mx[],a[rc].mx[]));

     a[o].my[]=max(a[o].my[],max(a[lc].my[],a[rc].my[]));

     a[o].my[]=min(a[o].my[],min(a[lc].my[],a[rc].my[]));

     a[o].sz=a[lc].sz+a[rc].sz+;

 }

 inline void news(int &o,node w){

     o=tp1?lit[tp1--]:++u; a[o].ad=w;

     lc=rc=; a[o].sz=;

     a[o].mx[]=a[o].mx[]=w.p[];

     a[o].my[]=a[o].my[]=w.p[];

 }

 void build(int &o,int l,int r,int wd){

     if(l>r) return ;

     int mid=l+((r-l)>>);

     d=wd;nth_element(b+l,b+mid,b+r+);

     news(o,b[mid]);

     build(lc,l,mid-,wd^),a[lc].fa=o;

     build(rc,mid+,r,wd^),a[rc].fa=o;

     up(o);

 }

 void pia(int o){

     if(lc) pia(lc);

     lit[++tp1]=o; b[++tp2]=a[o].ad;

     if(rc) pia(rc);

 }

 inline void check(int &o,int wd){

     if(alph*a[o].sz<max(a[lc].sz,a[rc].sz))

         tp2=,pia(o),build(o,,tp2,wd);

 }//是否不平衡需要重建

 void ins(int &o,int wd,node w){

     if(!o) {news(o,w); return ;}

     d=wd;ins(a[o].ch[a[o].ad<w],wd^,w);

     up(o);check(o,wd);

 }

 inline int gdis(int o,node w){

     if(!o) return inf;

     int res=;

     if(w.p[]>a[o].mx[]) res+=w.p[]-a[o].mx[];

     if(w.p[]<a[o].mx[]) res+=a[o].mx[]-w.p[];

     if(w.p[]>a[o].my[]) res+=w.p[]-a[o].my[];

     if(w.p[]<a[o].my[]) res+=a[o].my[]-w.p[];

     return res;

 }//点与矩形的最小距离

 inline int dis(node A,node B){

     return abs(A.p[]-B.p[])+abs(A.p[]-B.p[]);

 }

 void query(int o,node w){

     if(!o) return ;

     ans=min(ans,dis(a[o].ad,w));

     int D[]={gdis(lc,w),gdis(rc,w)},r=D[]>D[];

     if(D[r]<ans) query(a[o].ch[r],w);

     if(D[r^]<ans) query(a[o].ch[r^],w);

 }

 int main(){

     read(n);read(m);

     a[].mx[]=a[].my[]=-inf;

     a[].mx[]=a[].my[]=inf;

     for(register int i=;i<=n;++i) b[i].init();

     build(rt,,n,); node q1;

     for(register int i=,q2;i<=m;++i){

         read(q2); q1.init();

         if(q2==) ins(rt,,q1);

         else{

             ans=inf,query(rt,q1);

             print(ans); putchar('\n');

            }

     }return ;

 }