#include <bits/stdc++.h>
#define R(x) x = read()
#define double long double
#define pii pair<int,int>
#define iax INT_MAX
#define iin INT_MIN
#define lax LLONG_MAX
#define lin LLONG_MIN
#define sqrt sqrtl
bool Mbe;
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c){(pp-pbuf==1<<20)?fwrite(pbuf,1,1<<20,stdout),pp=pbuf,*pp++=c:*pp++=c;}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(long long x) {
    x<0&&(push('-'),x=-x);
    static int sta[60]={},top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
    char buf[1<<23],*p1=buf,*p2=buf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){ch=='-'&&(f=-1);ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
constexpr int N=1e6+100;
int n,m,h;
struct node{
    int x,y,t,id;
}v[N];
int t[N],ans[N];bool ety;
void upd(int i,int x){for(;i<=m+1;i+=(i&-i))t[i]=max(t[i],x);}
int ask(int i){int r=0;for(;i;i-=(i&-i))r=max(r,t[i]);return r;}
void clr(int i){for(;i<=m+1;i+=(i&-i))t[i]=0;}
void cdq(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    sort(v+l,v+mid+1,[](node x,node y){return x.y==y.y?x.t<y.t:x.y<y.y;});
    sort(v+mid+1,v+r+1,[](node x,node y){return x.y==y.y?x.t<y.t:x.y<y.y;});
    int i=l,j=mid+1;
    for(;j<=r;j++){
        if(!v[j].id)continue;
        while(i<=mid&&v[j].y>v[i].y){
            if(!v[i].id)upd(v[i].t,v[i].x+v[i].y),ety=1;
            i++;
        }
        if(ety)ans[v[j].id]=min(ans[v[j].id],v[j].x+v[j].y-ask(v[j].t));
    }
    for(int j=l;j<i;j++)if(!v[j].id)clr(v[j].t);
    ety=0;
}
bool Med;
signed main(){
#ifndef LOCAL
#else
    cerr << (&Med-&Mbe)/1024.0/1024 << "MB\n";
#endif
    int mx,my;mx=my=0;
    R(n);R(m);
    for(int i=1;i<=n;i++){
        R(int x),R(y);
        v[i]={x,y,1,0};
        mx=max(mx,x);
        my=max(my,y);
    }
    for(int i=1;i<=m;i++){
        R(int opt),R(x),R(y);
        v[i+n]={x,y,i+1,0};
        if(opt==2)v[i+n].id=++h;
        mx=max(mx,x);
        my=max(my,y);
    }
    fill(ans,ans+h+1,iax);
    sort(v+1,v+1+n+m,[](node x,node y){return x.x==y.x?x.y==y.y?x.t<y.t:x.y<y.y:x.x<y.x;});
    cdq(1,n+m);
    for(int i=1;i<=n+m;i++)v[i].x=mx-v[i].x+1;
    sort(v+1,v+1+n+m,[](node x,node y){return x.x==y.x?x.y==y.y?x.t<y.t:x.y<y.y:x.x<y.x;});
    cdq(1,n+m);
    for(int i=1;i<=n+m;i++)v[i].y=my-v[i].y+1;
    sort(v+1,v+1+n+m,[](node x,node y){return x.x==y.x?x.y==y.y?x.t<y.t:x.y<y.y:x.x<y.x;});
    cdq(1,n+m);
    for(int i=1;i<=n+m;i++)v[i].x=mx-v[i].x+1;
    sort(v+1,v+1+n+m,[](node x,node y){return x.x==y.x?x.y==y.y?x.t<y.t:x.y<y.y:x.x<y.x;});
    cdq(1,n+m);
    for(int i=1;i<=h;i++)write(ans[i]),push('\n');
    return 0;
}