Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n,m;

#define MAXN 500010

struct node

{

	int lc,rc,d[2],mx[2],mn[2];

	int siz;

	node(int x = 0,int y = 0){lc = rc = 0;d[0] = x;d[1] = y;}

	inline int& operator [](int x){return d[x];}

}t[MAXN << 1];

struct point

{

	int d[2];

}p[MAXN];

int ptr = 0;

int del[MAXN << 1],delptr = 0;

inline int newnode()

{

	if(delptr != 0)return del[delptr--];

	else return ++ptr;

}

int cmpd;

bool operator < (point a,point b){return a.d[cmpd] < b.d[cmpd];}

inline int dis(node a,node b){return abs(a[0] - b[0]) + abs(a[1] - b[1]);}

int root = 0;

inline void updata(int rt)

{

	t[rt].siz = t[t[rt].lc].siz + t[t[rt].rc].siz + 1;

	for(register int i = 0;i <= 1;++i)

	{

		if(t[rt].lc)

		{

			t[rt].mn[i] = min(t[rt].mn[i],t[t[rt].lc].mn[i]);

			t[rt].mx[i] = max(t[rt].mx[i],t[t[rt].lc].mx[i]);

		}

		if(t[rt].rc)

		{

			t[rt].mn[i] = min(t[rt].mn[i],t[t[rt].rc].mn[i]);

			t[rt].mx[i] = max(t[rt].mx[i],t[t[rt].rc].mx[i]);

		}

	}

	return;

}

void build(int &rt,int l,int r,int type)

{

	if(l > r)return;

	cmpd = type;

	rt = newnode();t[rt].siz = 1;

	register int mid = ((l + r) >> 1);

	nth_element(p + l,p + mid,p + r + 1);

	t[rt][0] = p[mid].d[0];t[rt][1] = p[mid].d[1];

	for(register int i = 0;i <= 1;++i)t[rt].mn[i] = t[rt].mx[i] = t[rt].d[i];

	build(t[rt].lc,l,mid - 1,type ^ 1);

	build(t[rt].rc,mid + 1,r,type ^ 1);

	updata(rt);

	return;

}

const double ALPHA = 0.8;

inline int create(node p)

{

	register int rt = newnode();t[rt] = p;t[rt].siz = 1;

	for(register int i = 0;i <= 1;++i)t[rt].mn[i] = t[rt].mx[i] = t[rt].d[i];

	return rt;

}

int tot;

void dfs(int rt)

{

	if(rt == 0)return;

	++tot;

	p[tot].d[0] = t[rt][0];p[tot].d[1] = t[rt][1];

	del[++delptr] = rt;

	dfs(t[rt].lc);dfs(t[rt].rc);

	memset(&t[rt],0,sizeof(t[rt]));

	return;

}

void insert(int &rt,node p,int type,bool flag)

{

	if(rt == 0){rt = create(p);return;}

	bool tag = false;

	if(p[type] <= t[rt][type])

	{

		tag = (t[t[rt].lc].siz + 1 >= (t[rt].siz + 1) * ALPHA);

		insert(t[rt].lc,p,type ^ 1,flag || tag);

	}

	else

	{

		tag = (t[t[rt].rc].siz + 1 >= (t[rt].siz + 1) * ALPHA);

		insert(t[rt].rc,p,type ^ 1,flag || tag);

	}

	if(!flag && tag)

	{

		tot = 0;dfs(rt);

		build(rt,1,tot,type);

		return;

	}

	updata(rt);

	return;

}

inline int get(node k,node x)

{

	register int sum = 0;

	for(register int i = 0;i <= 1;++i)sum += max(0,k.mn[i] - x[i]);

	for(register int i = 0;i <= 1;++i)sum += max(0,x[i] - k.mx[i]);

	return sum;

}

int ans = 0;

#define INF 0x3f3f3f3f

void query(int rt,node x)

{

	register int d,dl = INF,dr = INF;

	d = dis(t[rt],x);

	ans = min(ans,d);

	if(t[rt].lc)dl = get(t[t[rt].lc],x);

	if(t[rt].rc)dr = get(t[t[rt].rc],x);

	if(dl < dr)

	{

		if(dl < ans)query(t[rt].lc,x);

		if(dr < ans)query(t[rt].rc,x);

	}

	else

	{

		if(dr < ans)query(t[rt].rc,x);

		if(dl < ans)query(t[rt].lc,x);

	}

	return;

}

inline int query(node x)

{

	ans = INF;

	query(root,x);

	return ans;

}

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		p[i].d[0] = rd();p[i].d[1] = rd();

	}

	build(root,1,n,0);

	register int opt,x,y;

	for(register int i = 1;i <= m;++i)

	{

		opt = rd();x = rd();y = rd();

		if(opt == 2)printf("%d\n",query(node(x,y)));

		else insert(root,node(x,y),0,false);

	}

	return 0;

}