提交记录

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
struct question{
	int opt,t,x,y,ans;
	bool operator <(const question &qaq)	const{
		return t<qaq.t;
	}
}q[2*N];
int cnt,n,m;
struct tree{
	int l,r,v;
	bool lazy;
}t[4*N];
inline int lson(int u){
	return u<<1;
}
inline int rson(int u){
	return u<<1|1;
}
void push_up(int u){
	t[u].v=min(t[lson(u)].v,t[rson(u)].v);
}
void build(int u,int l,int r){
	t[u].l=l;
	t[u].r=r;
	t[u].v=2e9;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(lson(u),l,mid);
	build(rson(u),mid+1,r);
}
void update(int u,int x,int val){
	if(t[u].l==t[u].r){
	  t[u].lazy=0;
	  t[u].v=min(t[u].v,val);
	  return;
	}
	if(t[u].lazy){
	  t[u].lazy=0;
	  t[lson(u)].lazy=1;
	  t[lson(u)].v=2e9;
	  t[rson(u)].lazy=1;
	  t[rson(u)].v=2e9;
    }
	int mid=(t[u].l+t[u].r)>>1;
	if(x<=mid)update(lson(u),x,val);
	else update(rson(u),x,val);
	push_up(u);
}
int query(int u,int l,int r){
	if(t[u].lazy)return 2e9;
	if(t[u].l>=l&&t[u].r<=r)return t[u].v;
	int mid=(t[u].l+t[u].r)>>1,v=2e9;
	if(l<=mid)v=query(lson(u),l,r);
	if(r>mid)v=min(v,query(rson(u),l,r));
	return v;
}
//bool cmp1(question aa,question bb){
//	return aa.t<bb.t;
//}
question q2[N];
int len;
void cmp(int l,int r){
	len=0;
	int mid=(l+r)>>1;
	int s1=l,s2=mid+1;
	for(int i=l;i<=r;++i){
	  if(s1>mid){
	  	q2[++len]=q[s2];
	  	++s2;
	  }
	  else if(s2>r){
	  	q2[++len]=q[s1];
	  	++s1;
	  }
	  else if(q[s1].x<=q[s2].x){
	  	q2[++len]=q[s1];
	  	++s1;
	  }
	  else{
	  	q2[++len]=q[s2];
	  	++s2;
	  }
	}
	for(int i=l;i<=r;++i)q[i]=q2[i-l+1];
}
void cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	cmp(l,mid);
	cmp(mid+1,r);
	int j=l;
	for(int i=mid+1;i<=r;++i){
	  while(j<=mid&&q[j].x<=q[i].x){
	  	if(q[j].opt==1)update(1,q[j].y,-q[j].x-q[j].y);
	  	++j;
	  }
	  if(q[i].opt==2)q[i].ans=min(q[i].ans,q[i].x+q[i].y+query(1,0,q[i].y));
	}
	t[1].lazy=1;
	t[1].v=2e9;
}
//2
void cdq2(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq2(l,mid);
	cdq2(mid+1,r);
	cmp(l,mid);
	cmp(mid+1,r);
	int j=l;
	for(int i=mid+1;i<=r;++i){
	  while(j<=mid&&q[j].x<=q[i].x){
	  	if(q[j].opt==1)update(1,q[j].y,-q[j].x+q[j].y);
	  	++j;
	  }
	  if(q[i].opt==2)q[i].ans=min(q[i].ans,q[i].x-q[i].y+query(1,q[i].y,1e6));
	}
	t[1].lazy=1;
	t[1].v=2e9;
}
//3
void cmp2(int l,int r){
	len=0;
	int mid=(l+r)>>1;
	int s1=l,s2=mid+1;
	for(int i=l;i<=r;++i){
	  if(s1>mid){
	  	q2[++len]=q[s2];
	  	++s2;
	  }
	  else if(s2>r){
	  	q2[++len]=q[s1];
	  	++s1;
	  }
	  else if(q[s1].x>=q[s2].x){
	  	q2[++len]=q[s1];
	  	++s1;
	  }
	  else{
	  	q2[++len]=q[s2];
	  	++s2;
	  }
	}
	for(int i=l;i<=r;++i)q[i]=q2[i-l+1];
}
void cdq3(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq3(l,mid);
	cdq3(mid+1,r);
	cmp2(l,mid);
	cmp2(mid+1,r);
	int j=l;
	for(int i=mid+1;i<=r;++i){
	  while(j<=mid&&q[j].x>=q[i].x){
	  	if(q[j].opt==1)update(1,q[j].y,q[j].x+q[j].y);
	  	++j;
	  }
	  if(q[i].opt==2)q[i].ans=min(q[i].ans,-q[i].x-q[i].y+query(1,q[i].y,1e6));
	}
	t[1].lazy=1;
	t[1].v=2e9;
}
//4
void cdq4(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	cdq4(l,mid);
	cdq4(mid+1,r);
	cmp2(l,mid);
	cmp2(mid+1,r);
	int j=l;
	for(int i=mid+1;i<=r;++i){
	  while(j<=mid&&q[j].x>=q[i].x){
	  	if(q[j].opt==1)update(1,q[j].y,q[j].x-q[j].y);
	  	++j;
	  }
	  if(q[i].opt==2)q[i].ans=min(q[i].ans,-q[i].x+q[i].y+query(1,0,q[i].y));
	}
	t[1].lazy=1;
	t[1].v=2e9;
}
signed main(){
//	freopen("P4169_9.in","r",stdin);
//	freopen("out.out","w",stdout);
	cin>>n>>m;
	build(1,0,1e6);
	for(int i=1;i<=n;++i){
	  ++cnt;
	  cin>>q[cnt].x>>q[cnt].y;
	  q[cnt].opt=1;
	  q[cnt].t=cnt;
	}
	for(int i=1;i<=m;++i){
	  ++cnt;
	  cin>>q[cnt].opt>>q[cnt].x>>q[cnt].y;
	  q[cnt].ans=2e9;
	  q[cnt].t=cnt;
	  if(cnt<=30&&q[cnt].opt==2){
	  	for(int i=1;i<cnt;++i)if(q[i].opt==1)q[cnt].ans=min(q[cnt].ans,abs(q[cnt].x-q[i].x)+abs(q[cnt].y-q[i].y));
	  	cout<<q[cnt].ans<<"\n";
	  	--cnt;
	  }
	}
	cdq(1,cnt);
	sort(q+1,q+1+cnt);
	cdq2(1,cnt);
	sort(q+1,q+1+cnt);
	cdq3(1,cnt);
	sort(q+1,q+1+cnt);
	cdq4(1,cnt);
	sort(q+1,q+1+cnt);
	for(int i=1;i<=cnt;++i){
	  if(q[i].opt==2)cout<<q[i].ans<<"\n";
	}
	return 0;
}