// Author: gsczl71
// Copyright (c) 2024 gsczl71 All rights reserved.
// Problem: P3810 【模板】三维偏序（陌上花开）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3810
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// Date: 2024-03-23 14:15:35

// #pragma GCC optimize(2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fs first
#define sc second
#define x0 _x0_
#define y1 _y1_
#define endl '\n'
#define re register
#define pb push_back
#define vi vector<int>
#define pq priority_queue
#define mem(a,x) memset((a),(x),sizeof(a))
#define debug puts("AK IOI")
#define sz(s) (int)(s.size())
#define all(a) a.begin(),a.end()
#define rd(l,r) (myrand()%(r-l+1)+l)
#define print(x) {cout<<x<<endl;return;}
#define ctn(e) if(e) continue
#define brk(e) if(e) break
#define rt(e) if(e) return
#define ll_(e) (1ll*(e))
#define For(x,y,z) for(int x = y;x <= z;x++)
#define For_(x,y,z) for(int x = y;x >= z;x--)
using namespace std;
#define int long long
const int mod = 1e9+7;
//const int mod = 998244353;
mt19937 myrand(time(0));
const int inf = 0x3f3f3f3f,N = 1e6+5,M = 1e6+5,K = 3000+5;
const long long linf = 0x3f3f3f3f3f3f3f3f;
int n,k=1e6,m;
struct node{int a,b,c,op;};
struct data{node a;int cnt,ans,id;};
node a[N];
struct data b[N],bb[N];
int t[N<<1];
void add(int x,int val){while(x<=k)t[x]=max(t[x],val),x+=(x&-x);}
void clear(int x){while(x<=k)t[x]=0,x+=(x&-x);}
int query(int x){int res=0;while(x)res=max(res,t[x]),x-=(x&-x);return res?res:-1e18;}
bool node_cmp(node a,node b){
	if(a.a != b.a) return a.a<b.a;
	if(a.b != b.b) return a.b<b.b;
	return a.c<b.c;
}bool data_cmp(struct data a,struct data b){
	if(a.a.b != b.a.b) return a.a.b<b.a.b;
	return a.a.c<b.a.c;
}void cdq(int l,int r){
	if(l==r)return ;
	int mid=(l+r)>>1,x=l;
	cdq(l,mid),cdq(mid+1,r);
	sort(b+l,b+1+mid,data_cmp),sort(b+1+mid,b+1+r,data_cmp);
	For(i,mid+1,r){
		while(x<=mid&&b[x].a.b<=b[i].a.b) add(b[x].a.c,((b[x].cnt)?(b[x].a.b+b[x].a.c):0)),x++; //删了这一行就不会TLE但是显然会WA
		bb[b[i].id].ans=min(b[i].a.b+b[i].a.c-query(b[i].a.c),bb[b[i].id].ans);
	}For(i,l,x-1){
		clear(b[i].a.c);//清空还原操作
	}
}int ans[N];
int _n,_m;
pair<int,pii> que[N];
int len;
void sol_cdq(int x,int y){
	For(i,1,m){
		b[i]=bb[i];
		if(x) b[i].a.b=len-b[i].a.b;
		if(y) b[i].a.c=len-b[i].a.c;
	}
	cdq(1,m);
}
void solve(){
	cin>>_n>>_m;
	For(i,1,_n){
		cin>>a[i].b>>a[i].c;
		a[i].b++,a[i].c++;
		a[i].a=i;
	}
	For(i,_n+1,_n+_m){
		int op,x,y;cin>>op>>x>>y;x++,y++;
		a[i].b=x,a[i].c=y,a[i].a=i;
		if(op==2){
			a[i].op=1;
		}que[i]={op,{x,y}};	
	}
	n=_n+_m;
	sort(a+1,a+1+n,node_cmp);
	For(i,1,n){
		if(a[i].a!=a[i-1].a||a[i].b!=a[i-1].b||a[i].c!=a[i-1].c) bb[++m].a=a[i];
		if(!a[i].op)bb[m].cnt++;	
	}
	For(i,1,m) len = max({len,bb[i].a.b,bb[i].a.c});
	For(i,1,m) bb[i].id=i,bb[i].ans=1e18;
	// For(i,1,m) cout<<bb[i].a.a<<" "<<bb[i].a.b<<" "<<bb[i].a.c<<" "<<bb[i].cnt<<" "<<bb[i].ans<<" "<<bb[i].id<<endl;
	sol_cdq(0,0),sol_cdq(0,1),sol_cdq(1,0),sol_cdq(1,1);
	For(i,1,m)if(bb[i].a.op==1)cout<<bb[i].ans<<endl;
}
signed main(){
	// ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
//	cin >> T;
	For(_,1,T) solve();
	return 0;
}	

hack：

2 1
1 2
1 1
1 1 1