#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn = +;

 int x,y;

 int n,m;

 int ans;

 int cmp_d,root;

 struct node

 {

     int d[],MAX[],MIN[];

     int l,r;

 }t[];

 bool cmp(node a, node b)

 {

     return a.d[cmp_d]<b.d[cmp_d]||a.d[cmp_d]==b.d[cmp_d] && a.d[cmp_d^] < b.d[cmp_d^];

 }

 void PushUp(int p,int k)

 {

     t[p].MAX[]=max(t[p].MAX[],t[k].MAX[]);

     t[p].MAX[]=max(t[p].MAX[],t[k].MAX[]);

     t[p].MIN[]=min(t[p].MIN[],t[k].MIN[]);

     t[p].MIN[]=min(t[p].MIN[],t[k].MIN[]);

 }

 int build(int l,int r, int D)

 {

     int mid = (l+r) >> ;

     cmp_d = D;

     nth_element(t+l+,t+mid+,t+r+,cmp) ;

     t[mid].MAX[] = t[mid].MIN[] = t[mid].d[];

     t[mid].MAX[] = t[mid].MIN[] = t[mid].d[];

     if(l!=mid) t[mid].l = build(l,mid-,D^) ;

     else t[mid].l = ;

     if(r!=mid) t[mid].r = build(mid+,r,D^);

     else t[mid].r = ;

     if(t[mid].l) PushUp(mid,t[mid].l);

     if(t[mid].r) PushUp(mid,t[mid].r);

     return mid ;

 }

 void update(int k)

 {

     int p = root ;

     int D =  ;

     while(true)

     {

         PushUp(p,k);

         if(t[k].d[D] <= t[p].d[D])

         {

             if(!t[p].l)

             {

                 t[p].l = k ;

                 return;

             }

             p = t[p].l ;

         }

         else

         {

             if(!t[p].r){

                 t[p].r = k ;

                 return;

             }

             p = t[p].r ;

         }

         D ^= ;

     }

 }

 int getdis(int p,int x,int y)

 {

     int res = ;

     if(x > t[p].MAX[])res += x - t[p].MAX[];

     if(x < t[p].MIN[])res += t[p].MIN[] - x;

     if(y > t[p].MAX[])res += y - t[p].MAX[];

     if(y < t[p].MIN[])res += t[p].MIN[] - y;

     return res ;

 }

 void query(int p)

 {

     int d0 = abs(x - t[p].d[]) + abs(y - t[p].d[]) ;

     if(d0<ans) ans = d0 ;

     int dl , dr ;

     if(t[p].l) dl=getdis(t[p].l,x,y) ; else dl = INF ;

     if(t[p].r) dr=getdis(t[p].r,x,y) ; else dr = INF ;

     if(dl < dr)

     {

         if(dl < ans) query(t[p].l) ;

         if(dr < ans) query(t[p].r) ;

     }

     else

     {

         if(dr < ans) query(t[p].r) ;

         if(dl < ans) query(t[p].l) ;

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     scanf("%d%d",&n,&m);

     for(int i = ; i <= n ; i ++ )

         scanf("%d%d",&t[i].d[] , &t[i].d[]);

     if(n) root = build(,n,) ;

     for(int i = ; i <= m ; i ++ )

     {

         int q; scanf("%d%d%d",&q,&x,&y);

         if(q == )

         {

             n++ ;

             t[n].d[]=t[n].MAX[]=t[n].MIN[]=x;

             t[n].d[]=t[n].MAX[]=t[n].MIN[]=y;

             if(n>) update(n);

             else  root = build(,n,);

         }

         else

         {

             ans = INF;

             query(root);

             printf("%d\n",ans);

         }

     }

     return ;

 }