#include <bits/stdc++.h>
using namespace std;

const int N = 6e5 + 5, M = 1e6 + 1;

int n, m, id;
struct D { int op, t, x, y, s, ans; } d[N]; 
int f[N], idx, c[M + 5];

bool cmpt(D a, D b) { return a.t < b.t; }
bool cmpx(D a, D b) { return a.x < b.x; }

void change(int x, int v)
{
	while(x <= M)
	{
		c[x] = max(c[x], v);
		x += (x & -x); 
	}
}

void pop(int x)
{
	while(x <= M)
	{
		c[x] = 0;
		x += (x & -x); 
	}
}

int query(int x)
{
	int res = 0;
	while(x)
	{
		res = max(res, c[x]);
		x -= (x & -x);
	}
	return res;
}

void CDQ(int l, int r)
{
	if(l == r) return;
	int mid = (l + r) >> 1;
	CDQ(l, mid); CDQ(mid + 1, r); 
	sort(d + l, d + mid + 1, cmpx);
	sort(d + mid + 1, d + r + 1, cmpx);
	int i = l, j = mid + 1;
	while(j <= r)
	{
		while(i <= mid && d[i].x <= d[j].x) 
		{
			if(d[i].op == 1) 
				change(d[i].y, d[i].s);
			i ++;
		}
		if(d[j].op == 2)
			d[j].ans = min(d[j].ans, d[j].s - query(d[j].y)); 
		j ++;
	}
	for(j = l ; j < i ; j ++) if(d[j].op == 1) pop(d[j].y);
} 

int main()
{

//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++)
	{
		id ++; d[id].t = id;
		d[id].op = 1;
		cin >> d[id].x >> d[id].y;
		d[id].x ++; d[id].y ++;	
	} 
	for(int i = 1 ; i <= m ; i ++)
	{
		id ++; d[id].t = id;
		cin >> d[id].op; 
		if(d[id].op == 2) f[ ++ idx] = id;
		cin >> d[id].x >> d[id].y; 
		d[id].x ++; d[id].y ++;	
	}
	
	for(int i = 1 ; i <= id ; i ++) 
		d[i].ans = M << 2;
	
	for(int T = 1 ; T <= 4 ; T ++)
	{
		for(int i = 1 ; i <= id ; i ++)
		{
			int x = d[i].x, y = d[i].y;
			d[i].x = M - y + 1; d[i].y = x;
			d[i].s = d[i].x + d[i].y;
		}
		CDQ(1, id);
		sort(d + 1, d + id + 1, cmpt);
	}
	
	for(int i = 1 ; i <= idx ; i ++)
		cout << d[f[i]].ans << "\n";

	return 0;
}