RT

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

namespace IO{
	int f; char c;

	template<typename T> inline void read(T &v){
		v = 0; f = 1; c = getchar();
		while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
		while(isdigit(c)) { v = (v << 3) + (v << 1) + (int)(c - '0'); c = getchar(); }
		v *= f;
		return;
	}

	template<typename T> inline void write(T k){
		if(k < 0) { putchar('-'); k = -k; }
		if(k > 9) write(k / 10);
		putchar((char)(k % 10 + '0'));
		return;
	}

	inline int Read() { int v; read(v); return v; }
	inline void Write(int v, char ed = '\n') { write(v); putchar(ed); return; }
}

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)

using IO::read;
using IO::Write;

const int N=1e6+5, INF=0x3f3f3f3f;

struct Point{
	int x[2];
};

struct Node{
	int l, r;
	Point P;
	int L[2], R[2], sz;
	
	#define ls tr[u].l
	#define rs tr[u].r
}tr[N];

int n, m;

int idx, root;
int buf[N], tot;
int add(){
	if(!tot) return ++idx;
	return buf[tot--];
}

void pushup(int u){
	auto &L=tr[ls], &R=tr[rs];
	tr[u].sz=L.sz+R.sz+1;

	rep(i,0,1){
		tr[u].L[i]=min(tr[u].P.x[i], min(L.L[i], R.L[i]));
		tr[u].R[i]=max(tr[u].P.x[i], max(L.R[i], R.R[i]));
	}
}

const double Al=0.75;

Point pt[N];

void getSeq(int u, int cnt){
	if(ls) getSeq(ls, cnt);
	buf[++tot]=u, pt[tr[ls].sz+1+cnt]=tr[u].P;
	if(rs) getSeq(rs, cnt+tr[ls].sz+1);
}

int rebuild(int l, int r, int k){
	if(l>r) return 0;
	int mid=l+r>>1;
	int u=add();
	
	nth_element(pt+l, pt+mid, pt+r+1, [&](Point a, Point b){
		return a.x[k]<b.x[k];
	});
	tr[u].P=pt[mid];
	
	ls=rebuild(l, mid-1, k^1), rs=rebuild(mid+1, r, k^1);
	pushup(u);
	return u;
}

void maintain(int &u, int k){
	if(tr[u].sz*Al<tr[ls].sz || tr[u].sz*Al<tr[rs].sz)
		getSeq(u, 0), u=rebuild(1, tot, k);	
}

void insert(int &u, Point p, int k){
	if(!u){
		u=add();
		tr[u].l=tr[u].r=0;
		tr[u].P=p, pushup(u);
		return;
	}
	if(p.x[k]<=tr[u].P.x[k]) insert(ls, p, k^1);
	else insert(rs, p, k^1);
	pushup(u);
	maintain(u, k);
}

int dis(Point a, Point b){
	return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);
}

int H(Node t, Point p){
	int x=p.x[0], y=p.x[1];
	return max(0, t.L[0]-x)+max(0, t.L[1]-y)+max(0, x-t.R[0])+max(0, y-t.R[1]);
}

int res;

void queryin(int u, Point p){
	if(!u) return;
	res=min(res, dis(tr[u].P, p));
	int LV=INF, RV=INF;
	if(ls) LV=H(tr[ls], p);
	if(rs) RV=H(tr[rs], p);
	
	if(LV<RV){
		if(LV<res) queryin(ls, p);
		if(RV<res) queryin(rs, p);
	}
	else{
		if(RV<res) queryin(rs, p);
		if(LV<res) queryin(ls, p);
	}
}

void queryax(int u, Point p){
	if(!u) return;
	res=max(res, dis(tr[u].P, p));
	int LV=-INF, RV=-INF;
	if(ls) LV=H(tr[ls], p);
	if(rs) RV=H(tr[rs], p);
	
	if(LV>RV){
		if(LV>res) queryax(ls, p);
		if(RV>res) queryax(rs, p);
	}
	else{
		if(RV>res) queryax(rs, p);
		if(LV>res) queryax(ls, p);
	}
}

int main(){
	cin>>n;
	tr[0].L[0]=tr[0].L[1]=N+5;
	tr[0].R[0]=tr[0].R[1]=-1;
	
	rep(i,1,n){
		int x, y; read(x), read(y);
		pt[i]={x, y};
	}
	root=rebuild(1, n, 0);
	cin>>m;
	rep(i,1,m){
		int op, x, y; read(op), read(x), read(y);
		if(op==0) insert(root, {x, y}, 0);
		else if(op==1){
			res=INF;
			queryin(root, {x, y});
			Write(res);
		}else if(op==2){
            res=-INF;
			queryax(root, {x, y});
			Write(res);
        }
	}

	return 0;
}

5个WA 20个TLE 样例过了