#include<cstdio>

#include<cstring>

#include<algorithm>

#define read(x) x=getint()

using namespace std;

const int N = 500003;

const int inf = 0x7fffffff;

int getint() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - '0';

	return k * fh;

}

bool D;

int n, t, root, ans;

struct KDT {

	int d[2], ch[2], minn[2], maxn[2];

	bool operator < (const KDT &a) const {return d[D] < a.d[D];}

	void init() {for(int i = 0; i < 2; ++i) minn[i] = maxn[i] = d[i];}

} T[N << 1], QQ;

void pushup(int rt) {

	for(int i = 0; i < 2; ++i)

		if (T[rt].ch[i]) {

			int x = T[rt].ch[i];

			for(int j = 0; j < 2; ++j)

				T[rt].minn[j] = min(T[rt].minn[j], T[x].minn[j]),

				T[rt].maxn[j] = max(T[rt].maxn[j], T[x].maxn[j]);

		}

}

int Build(int l = 1, int r = n, bool d = 0) {

	D = d; int mid = (l + r) >> 1; nth_element(T + l, T + mid, T + r + 1);

	T[mid].init();

	if (l != mid) T[mid].ch[0] = Build(l, mid - 1, !d);

	if (r != mid) T[mid].ch[1] = Build(mid + 1, r, !d);

	pushup(mid);

	return mid;

}

int ask(int rt, KDT p) {

	int ret = 0;

	for(int i = 0; i < 2; ++i)

		ret += max(0, T[rt].minn[i] - p.d[i]), ret += 	max(0, p.d[i] - T[rt].maxn[i]);

	return ret;

}

void insert(int rt = root, bool d = 0) {

	bool flag = T[n].d[d] > T[rt].d[d];

	if (T[rt].ch[flag]) insert(T[rt].ch[flag], !d);

	else T[rt].ch[flag] = n;

	pushup(rt);

}

int dis(KDT a, KDT b) {

	return abs(a.d[0] - b.d[0]) + abs(a.d[1] - b.d[1]);

}

void Query(int rt = root, bool d = 0) {

	int Dis = dis(T[rt], QQ), dl = inf, dr = inf;

	ans = min(ans, Dis);

	if (T[rt].ch[0]) dl = ask(T[rt].ch[0], QQ);

	if (T[rt].ch[1]) dr = ask(T[rt].ch[1], QQ);

	if (dl < dr) {

		if (dl < ans) Query(T[rt].ch[0], !d);

		if (dr < ans) Query(T[rt].ch[1], !d);

	} else {

		if (dr < ans) Query(T[rt].ch[1], !d);

		if (dl < ans) Query(T[rt].ch[0], !d);

	}

}

int main() {

	read(n); read(t);

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

		read(T[i].d[0]), read(T[i].d[1]);

	int num;

	for(root = Build(); t; --t) {

		read(num); ans = inf;

		if (num == 1) {

			read(T[++n].d[0]); read(T[n].d[1]);

			T[n].init();

			insert();

		} else {

			read(QQ.d[0]); read(QQ.d[1]);

			Query();

			printf("%d\n", ans);

		}

	}

	return 0;

}