#include<bits/stdc++.h>
const int maxn=3e5+10;
const int maxm=1e6+10;
const int INF=0x3f3f3f3f;
using namespace std;
struct s{
	int x,y,z;
	int op;
	int pos;
}a1[maxn<<1];
s a2[maxn<<1],a3[maxn<<1],a4[maxn<<1],a5[maxn<<1];
s e[maxn<<1];
int c1[maxm],c2[maxm],c3[maxm],c4[maxm];
int n,m;
int f[maxn],cnt=0,ct2=0;
bool cmp(s a,s b){
	return a.x<b.x ;
}//
//维护四个三维偏序，就是在xy的左右上下四个方向的点,时间上是先出现的可以更新后出现的
//树桩数组维护前缀最大最小
//PS：逆向思维：树状数组只能维护前缀最大最小值，那么如果我要维护比我大的，那么扔进下标1e6-pos就可以了
int lowbit(int x){
	return x&(-x);
}
void add(int c[],int x,int val,int op){
	for(int i=x;i<=maxm;i=i+lowbit(i)){
		if(op==1) c[i]=max(c[i],val);
		if(op==2) c[i]=min(c[i],val);
		if(op==3) c[i]=min(c[i],val);
		if(op==4) c[i]=min(c[i],val);
	} 
}
int query(int c[],int x,int op){
	int maxn=0;
	if(op==1){
		for(int i=x;i ;i-=lowbit(i))
			maxn=max(maxn,c[i]);
		return maxn;
	}
	else{
		maxn=INF;
		for(int i=x;i; i-=lowbit(i))
			maxn=min(maxn,c[i]);
		return maxn;
	}
}
void clear(int c[],int x,int op){
	for(int i=x;i<=maxm;i+=lowbit(i)){
		if(op==1) {
			if(c[i]==0) return ;
			c[i]=0;
		}
		else{
		//
			if(c[i]==INF) return ;
			c[i]=INF;
		} 
	}
}
void merge(int l,int r,s a[],int c[],int opt){
	int mid=l+r>>1;
	int t1=l,t2=mid+1,pos=l-1;
	while(t2<=r){
		if(opt==1){// zuo xia-->x+y-max(xi+yi)
			while(t1<=mid&&a[t1].y<=a[t2].y){	
				if(a[t1].op==1)//在内就
					add(c,a[t1].z,a[t1].z+a[t1].y,opt);
				e[++pos]=a[t1];
				t1++;
			}
		}
		if(opt==2){// you shang   min(xi+yi)-(x+y)
			while(t1<=mid&&a[t1].y>a[t2].y){	
				if(a[t1].op==1)//这里用一个技巧：因为a[t2].y<a[t1].y,所以取反偏移，就可以实现 1e6-a[t2].y>1e6-a[t1].y
					add(c,maxm-a[t1].z,a[t1].z+a[t1].y,opt);
				e[++pos]=a[t1];
				t1++;
			}
		}
		if(opt==3){// zuo shang x-y+min(yi-xi)
			while(t1<=mid&&a[t1].y<=a[t2].y){	
				if(a[t1].op==1)
					add(c,maxm-a[t1].z,a[t1].z-a[t1].y,opt);
				e[++pos]=a[t1];
				t1++;
			}
		}
		if(opt==4){// you xia --> y-x+min(xi-yi)
			while(t1<=mid&&a[t1].y>a[t2].y){	
				if(a[t1].op==1)
					add(c,a[t1].z,a[t1].y-a[t1].z,opt);
				e[++pos]=a[t1];
				t1++;
			}
		}

		e[++pos]=a[t2];
		if(a[t2].op==1 ){
			t2++;
			continue;
		} 
		int _add;
		if(opt==1) {
			_add=query(c,a[t2].z ,opt);
			f[a[t2].pos]=min(f[a[t2].pos],a[t2].y+a[t2].z-_add);
		}	
		if(opt==2) {
			_add=query(c,maxm-a[t2].z,opt);	
			f[a[t2].pos]=min(f[a[t2].pos],_add-a[t2].y-a[t2].z);
		}  
		if(opt==3) {
			_add=query(c,maxm-a[t2].z,opt);
			f[a[t2].pos]=min(f[a[t2].pos],_add+a[t2].y-a[t2].z);
		}  
		if(opt==4) {
			_add=query(c,a[t2].z,opt);
			f[a[t2].pos]=min(f[a[t2].pos],_add+a[t2].z-a[t2].y);
		}  
		t2++;
	}
	
	for(int i=t1;i<=mid;i++)
		e[++pos]=a[i];
	for(int i=l;i<t1;i++){
		if(a[i].op==2) continue;
		if(opt==1) clear(c,a[i].z,opt);
		if(opt==2) clear(c,maxm-a[i].z,opt);
		if(opt==3) clear(c,maxm-a[i].z,opt);	
		if(opt==4) clear(c,a[i].z,opt);
	}
	for(int i=l;i<=r;i++)
		a[i]=e[i];
}
//树桩数组维护什么--》再化一步（针对数学的式子）
void cdq(int l,int r){
	if(l==r) return ;
	int mid=l+r>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	merge(l,r,a1,c1,1);
	merge(l,r,a2,c2,2);
	merge(l,r,a3,c3,3);
	merge(l,r,a4,c4,4);
}
int main(){
//	freopen("A.in","r",stdin);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d %d",&a1[i].y,&a1[i].z );
		a1[i].y++;
		a1[i].z++;
		a1[i].x=a1[i].pos=0;
		a1[i].op=1;
		a2[i]=a3[i]=a4[i]=a5[i]=a1[i];
	}
	ct2=n;
	for(int i=1;i<=m;i++){
		ct2++;
		scanf("%d %d %d ",&a1[ct2].op,&a1[ct2].y,&a1[ct2].z );

		a1[ct2].y++;
		a1[ct2].z++;
		a1[ct2].x=i;
		if(a1[ct2].op==2) a1[ct2].pos=++cnt;
		else a1[ct2].pos=0;
		
		a2[ct2]=a3[ct2]=a4[ct2]=a5[ct2]=a1[ct2];
	}
	sort(a1+1,a1+1+ct2,cmp);
	sort(a2+1,a2+1+ct2,cmp);
	sort(a3+1,a3+1+ct2,cmp);
	sort(a4+1,a4+1+ct2,cmp);
	memset(f,0x3f,sizeof(f));
	memset(c2,0x3f,sizeof(c2));
	memset(c3,0x3f,sizeof(c3));
	memset(c4,0x3f,sizeof(c4));
	cdq(1,ct2);
		
	for(int i=1;i<=ct2;i++){
		if(a5[i].op ==1) continue;
		printf("%d\n",f[a5[i].pos] );
	}
	return 0;
}