#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

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;

}

#define N 300010

#define M 1000010

#define inf 10000000

int n,m,p,tree[M],stk[N<<],top=;

struct data

{

    int op,x,y,i,ans;

    bool operator <(const data&a) const

    {

        return x<a.x||x==a.x&&i<a.i;

    }

}q[N],t[N];

struct data2

{

    int x,y;

    bool operator <(const data2&a) const

    {

        return x<a.x;

    }

}a[N];

bool cmp(const data&a,const data&b)

{

    return a.i<b.i;

}

void update(int k,int x){while (k<=p){stk[++top]=k;tree[k]=max(tree[k],x);k+=k&-k;}}

int getans(int k){int s=-inf;while (k){s=max(s,tree[k]);k-=k&-k;}return s;}

void solve(int l,int r)

{

    if (l==r) return;

    int mid=l+r>>;

    solve(l,mid);

    solve(mid+,r);

    int i=l,j=mid+;

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

    if (q[i]<q[j]&&i<=mid||j>r) t[k]=q[i++];

    else t[k]=q[j++];

    for (int k=l;k<=r;k++) q[k]=t[k];

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

    if (q[k].op==&&q[k].i<=mid) update(q[k].y,q[k].x+q[k].y);

    else if (q[k].op==&&q[k].i>mid) q[k].ans=min(q[k].ans,q[k].x+q[k].y-getans(q[k].y));

    while (top) tree[stk[top--]]=-inf;

}

void work()

{

    memset(tree,,sizeof(tree));

    sort(a,a+m+);sort(q,q+n+);

    int j=;

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

    if (q[i].op==)

    {

        while (j<m&&a[j+].x<=q[i].x) j++,update(a[j].y,a[j].x+a[j].y);

        q[i].ans=min(q[i].ans,q[i].x+q[i].y-getans(q[i].y));

    }

    memset(tree,,sizeof(tree));

    sort(q,q+n+,cmp);

    top=;

    solve(,n);

}

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

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

    for (int i=;i<=m;i++) p=max(p,max(a[i].x=read()+,a[i].y=read()+)+);

    for (int i=;i<=n;i++) q[i].op=read(),p=max(p,max(q[i].x=read()+,q[i].y=read()+)+),q[i].i=i,q[i].ans=inf;

    work();

    for (int i=;i<=m;i++) a[i].x=p-a[i].x;

    for (int i=;i<=n;i++) q[i].x=p-q[i].x;

    work();

    for (int i=;i<=m;i++) a[i].y=p-a[i].y;

    for (int i=;i<=n;i++) q[i].y=p-q[i].y;

    work();

    for (int i=;i<=m;i++) a[i].x=p-a[i].x;

    for (int i=;i<=n;i++) q[i].x=p-q[i].x;

    work();

    sort(q+,q+n+,cmp);

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

    if (q[i].op==) printf("%d\n",q[i].ans);

    return ;

}