#include<bits/stdc++.h>
using namespace std;
long long n, m, c[600010], ans[600010], len;
struct node{
	long long x, y, z, op, sum;
}a[600010];
bool cmp1(node x, node y){
	if(x.x!=y.x)return x.x<y.x;
	if(x.y!=y.y)return x.y<y.y;
	return x.z<y.z;
}
bool cmp2(node x, node y){
	if(x.x!=y.x)return x.x>y.x;
	if(x.y!=y.y)return x.y<y.y;
	return x.z<y.z;
}
bool cmp3(node x, node y){
	if(x.x!=y.x)return x.x<y.x;
	if(x.y!=y.y)return x.y>y.y;
	return x.z<y.z;
}
bool cmp4(node x, node y){
	if(x.x!=y.x)return x.x>y.x;
	if(x.y!=y.y)return x.y>y.y;
	return x.z<y.z;
}
bool cmp5(node x, node y){
	if(x.y!=y.y)return x.y<y.y;
	return x.z<y.z;
}
bool cmp6(node x, node y){
	if(x.y!=y.y)return x.y>y.y;
	return x.z<y.z;
}
int lowbit(int x){
	return x&-x;
}
void add(int pos, long long x){
	while(pos<=len){
		c[pos]=max(x,c[pos]);
		pos+=lowbit(pos);
	}
}
long long sum(int pos){
	long long ans=INT_MIN;
	while(pos){
		ans=max(c[pos],ans);
		pos-=lowbit(pos);
	}
	return ans;
}
void cl(int pos){
	while(pos<=len){
		c[pos]=INT_MIN;
		pos+=lowbit(pos);
	}
}
void solve1(int l, int r){
	if(l==r)return;
	int mid=(l+r)/2;
	solve1(l,mid);solve1(mid+1,r);
	sort(a+l,a+mid+1,cmp5);sort(a+mid+1,a+r+1,cmp5);
	int i=l, j=mid+1;
	while(j<=r){
		while(i<=mid&&a[i].y<=a[j].y){
			if(!a[i].op)
			add(a[i].z,a[i].x+a[i].y);
			i++;
		}
		if(a[j].op)a[j].sum=min(-sum(a[j].z)+a[j].x+a[j].y,a[j].sum);
		j++;
	}
	for(int k=l;k<i;k++)cl(a[k].z);
}
void solve2(int l, int r){
	if(l==r)return;
	int mid=(l+r)/2;
	solve2(l,mid);solve2(mid+1,r);
	sort(a+l,a+mid+1,cmp5);sort(a+mid+1,a+r+1,cmp5);
	int i=l, j=mid+1;
	while(j<=r){
		while(i<=mid&&a[i].y<=a[j].y){
			if(!a[i].op)
			add(a[i].z,a[i].y-a[i].x);
			i++;
		}
		if(a[j].op)a[j].sum=min(-sum(a[j].z)-a[j].x+a[j].y,a[j].sum);
		j++;
	}
	for(int k=l;k<i;k++)cl(a[k].z);
}
void solve3(int l, int r){
	if(l==r)return;
	int mid=(l+r)/2;
	solve3(l,mid);solve3(mid+1,r);
	sort(a+l,a+mid+1,cmp6);sort(a+mid+1,a+r+1,cmp6);
	int i=l, j=mid+1;
	while(j<=r){
		while(i<=mid&&a[i].y>=a[j].y){
			if(!a[i].op)
			add(a[i].z,a[i].x-a[i].y);
			i++;
		}
		if(a[j].op)a[j].sum=min(-sum(a[j].z)+a[j].x-a[j].y,a[j].sum);
		j++;
	}
	for(int k=l;k<i;k++)cl(a[k].z);
}
void solve4(int l, int r){
	if(l==r)return;
	int mid=(l+r)/2;
	solve4(l,mid);solve4(mid+1,r);
	sort(a+l,a+mid+1,cmp6);sort(a+mid+1,a+r+1,cmp6);
	int i=l, j=mid+1;
	while(j<=r){
		while(i<=mid&&a[i].y>=a[j].y){
			if(!a[i].op)
			add(a[i].z,-a[i].x-a[i].y);
			i++;
		}
		if(a[j].op)a[j].sum=min(-sum(a[j].z)-a[j].x-a[j].y,a[j].sum);
		j++;
	}
	for(int k=l;k<i;k++)cl(a[k].z);
}
bool cmp(node x, node y){
	return x.z<y.z;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		len++;
		cin>>a[len].x>>a[len].y;
		a[len].z=len;
	}
	for(int i=1;i<=m;i++){
		int op, x, y;
		cin>>op>>x>>y;
		len++;
		if(op==1){
			a[len].x=x;a[len].y=y;
			a[len].z=len;
		}
		else{
			a[len].x=x;a[len].y=y;
			a[len].z=len;a[len].op=1;a[len].sum=INT_MAX;
		}
	}
	sort(a+1,a+1+len,cmp1);
	solve1(1,len);
	sort(a+1,a+1+len,cmp2);
	solve2(1,len);
	sort(a+1,a+1+len,cmp3);
	solve3(1,len);
	sort(a+1,a+1+len,cmp4);
	solve4(1,len);
	sort(a+1,a+1+len,cmp);
	for(int i=1;i<=len;i++)if(a[i].op)cout<<a[i].sum<<endl;
	return 0;
}