#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int res=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
	return res*f;
}
void write(int x)
{
	if(x<0){x=-x;putchar('-');}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct node
{
	int x,y,op,id;
}q[114514<<3];
bool cmp(node x,node y)
{
	return x.x<y.x;
}
int t[5][1145141];
inline int lowbit(int x)
{
	return x&-x;
}
inline void add(int x,int k,int id)
{
	for(;x<=1e6;x+=lowbit(x))
		t[id][x]=min(t[id][x],k);
}
inline void clear(int x,int id)
{
	for(;x<=1e6;x+=lowbit(x))
		t[id][x]=1e9;
}
inline int query(int x,int id) 
{
	int res=1e9;
	for(;x;x-=lowbit(x))
		res=min(res,t[id][x]);
	return res;
}
int n,m;
int cnt;
int ans[114514<<3];
void cdq_solve(int l,int r)
{
	if(l>=r)
		return;
	int mid=l+r>>1;
	cdq_solve(l,mid);
	cdq_solve(mid+1,r);
	sort(q+l,q+mid+1,cmp);
	sort(q+mid+1,q+r+1,cmp);
	for(int i=l;i<=mid;i++)
	{
		if(q[i].op==2)
			continue;
		add(1e6-q[i].y+1,-q[i].x+q[i].y,1);
		add(1e6-q[i].y+1,q[i].x+q[i].y,2);
		add(q[i].y+1,-q[i].x-q[i].y,3);
		add(q[i].y+1,q[i].x-q[i].y,4);
	}
	for(int i=mid+1;i<=r;i++)
	{
		if(q[i].op==1)
			continue;
		if(query(1e6-q[i].y+1,1)+q[i].x-q[i].y>0)
			ans[q[i].id]=min(ans[q[i].id],query(1e6-q[i].y+1,1)+q[i].x-q[i].y);
		if(query(1e6-q[i].y+1,2)-q[i].x-q[i].y>0)
			ans[q[i].id]=min(ans[q[i].id],query(1e6-q[i].y+1,2)-q[i].x-q[i].y);
		if(query(q[i].y+1,3)+q[i].x+q[i].y>0)
			ans[q[i].id]=min(ans[q[i].id],query(q[i].y+1,3)+q[i].x+q[i].y);
		if(query(q[i].y+1,4)-q[i].x+q[i].y>0)
			ans[q[i].id]=min(ans[q[i].id],query(q[i].y+1,4)-q[i].x+q[i].y);
	}
	for(int i=l;i<=mid;i++)
	{
		if(q[i].op==2)
			continue;
		clear(1e6-q[i].y+1,1);
		clear(1e6-q[i].y+1,2);
		clear(q[i].y+1,3);
		clear(q[i].y+1,4);
	}
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		q[++cnt].op=1,q[cnt].x=read(),q[cnt].y=read();
	for(int i=1;i<=m;i++)
		q[++cnt].op=read(),q[cnt].x=read(),q[cnt].y=read(),q[cnt].id=i;
	memset(ans,0x3f,sizeof ans);
	memset(t,0x3f,sizeof t);
	cdq_solve(1,cnt);
	for(int i=1;i<=cnt;i++)
		if(q[i].op==2)
			write(ans[q[i].id]),puts("");
}