#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 1000010

#define inf 2000000000

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

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

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,root,cnt,c,ans;

struct point

{

    int d[],tag;

    bool operator <(const point&a) const

    {

        return d[c]<a.d[c];

    }

}a[N];

struct KDTree{int ch[],a[][],tag;point p;

}tree[N];

struct data{int op;point p;

}q[N];

inline int dis(point u,point v){return abs(u.d[]-v.d[])+abs(u.d[]-v.d[]);}

inline void chkmin(int &x,int y){x=min(x,y);}

inline void chkmax(int &x,int y){x=max(x,y);}

inline bool isin(point x,int a[][]){return a[][]<=x.d[]&&a[][]>=x.d[]&&a[][]<=x.d[]&&a[][]>=x.d[];}

inline int max(int x,int y,int z){return max(max(x,y),z);}

inline int guess(point x,int a[][]){return max(,a[][]-x.d[],x.d[]-a[][])+max(,a[][]-x.d[],x.d[]-a[][]);}

void build(int &k,int l,int r,int op)

{

    if (l>r) return;

    k=++cnt;c=op;int mid=l+r>>;

    nth_element(a+l,a+mid,a+r+);

    tree[k].p=a[mid],tree[k].tag=a[mid].tag,

    tree[k].a[][]=tree[k].a[][]=a[mid].d[],

    tree[k].a[][]=tree[k].a[][]=a[mid].d[];

    for (int i=l;i<=r;i++)

    chkmin(tree[k].a[][],a[i].d[]),chkmax(tree[k].a[][],a[i].d[]),

    chkmin(tree[k].a[][],a[i].d[]),chkmax(tree[k].a[][],a[i].d[]);

    build(tree[k].ch[],l,mid-,op^);

    build(tree[k].ch[],mid+,r,op^);

}

void ins(int k,point x)

{

    if (!k) return;

    if (tree[k].p.d[]==x.d[]&&tree[k].p.d[]==x.d[]) {tree[k].tag=;return;}

    if (isin(x,tree[tree[k].ch[]].a)) ins(tree[k].ch[],x);

    if (isin(x,tree[tree[k].ch[]].a)) ins(tree[k].ch[],x);

}

void query(int k,point x)

{

    if (!k) return;

    if (tree[k].tag) chkmin(ans,dis(x,tree[k].p));

    int p=tree[k].ch[],q=tree[k].ch[],u=guess(x,tree[p].a),v=guess(x,tree[q].a);

    if (v<u) swap(p,q),swap(u,v);

    if (u<ans) query(p,x);

    if (v<ans) query(q,x);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2648.in","r",stdin);

    freopen("bzoj2648.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++) a[i].d[]=read(),a[i].d[]=read(),a[i].tag=;

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

    {

        q[i].op=read(),q[i].p.d[]=read(),q[i].p.d[]=read();

        if (q[i].op==) a[++n]=q[i].p;

    }

    build(root,,n,);

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

    if (q[i].op==) ins(root,q[i].p);

    else ans=inf,query(root,q[i].p),printf("%d\n",ans);

    return ;

}