我真的觉得数据结构题好难啊，我做错了什么吗？居然还卡我的常数！/kk

咳咳进入正题。。。

91 分，T #10，实在卡不动了，求助。。。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast", "-funroll-loops")
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
	register char c = getchar();
	register int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

struct Point {
	int _time, x, y, type;
	Point() {}
	Point(int _time, int x, int y, int type) : _time(_time), x(x), y(y), type(type) {}
	bool operator < (const Point& p) const {return _time < p._time;}
};
Point p[1000005], q[1000005];
int n, m, c[2000055], ans[500005];

inline int Lowbit(int x) {
	return x & -x;
}

inline void Update(int i, int x) {
	//printf("Update(%d,%d)\n", i, x);
	for (register int j = i;j <= 1000010;j += Lowbit(j)) c[j] = Max(c[j], x);
}

inline void Remove(int i) {
	for (register int j = i;j <= 1000010;j += Lowbit(j)) {
		if (c[j]) c[j] = 0;
		else return;
	}
}

inline int Query(int i) {
	//printf("Query(%d)", i);
	register int ans = 0;
	for (register int j = i;j >= 1;j -= Lowbit(j)) ans = Max(ans, c[j]);
	//printf("=%d\n", ans);
	return ans;
}

inline void Read() {
	n = qread(); m = qread();
	for (register int i = 1;i <= n;i++) {
		register int x = qread() + 1, y = qread() + 1;
		p[i] = Point(0, x, y, 1);
	}
	for (register int i = 1;i <= m;i++) {
		register int opt = qread(), x = qread() + 1, y = qread() + 1;
		p[i + n] = Point(i, x, y, opt);
	}
}

inline void cdq1(int l, int r) {
	if (l == r) return;
	register int mid = l + r >> 1;
	cdq1(l, mid);
	cdq1(mid + 1, r);
	register int i = l, j = mid + 1;
	vector <Point> vc;
	//printf("cdq(%d,%d)\n", l, r);
	//puts("{");
	//for (register int i = l;i <= r;i++) printf("%d %d %d\n", p[i].type, p[i].x, p[i].y);
	while (i <= mid && j <= r) {
		if (p[i].x <= p[j].x) {
			if (p[i].type == 1) {
				Update(p[i].y, p[i].x + p[i].y);
			}
			vc.push_back(p[i]);
			i++;
		} else {
			if (p[j].type == 2) {
				//printf("%d %d\n", p[j].x + p[j].y, Query(p[j].y));
				register int tmp = Query(p[j].y);
				if (tmp) ans[p[j]._time] = Min(ans[p[j]._time], p[j].x + p[j].y - tmp);
			}
			vc.push_back(p[j]);
			j++;
		}
	}
	while (i <= mid) vc.push_back(p[i]), i++;
	while (j <= r) {
		if (p[j].type == 2) {
			//printf("%d %d\n", p[j].x + p[j].y, Query(p[j].y));
			register int tmp = Query(p[j].y);
			if (tmp) ans[p[j]._time] = Min(ans[p[j]._time], p[j].x + p[j].y - tmp);
		}
		vc.push_back(p[j]);
		j++;
	}
	//puts("}");
	for (i = l;i <= mid;i++) {
		if (p[i].type == 1) Remove(p[i].y);
	}
	for (i = l;i <= r;i++) p[i] = vc[i - l];
}

inline void Solve() {
	memcpy(q, p, sizeof(q));
	cdq1(1, n + m);
	//for (register int i = 1;i <= m;i++) {
	//	if (ans[i] != 0x3f3f3f3f) printf("%d\n", ans[i]);
	//}
	memcpy(p, q, sizeof(p));
	for (register int i = 1;i <= n + m;i++) p[i].x = 1000002 - p[i].x;
	cdq1(1, n + m);
	memcpy(p, q, sizeof(p));
	for (register int i = 1;i <= n + m;i++) p[i].y = 1000002 - p[i].y;
	cdq1(1, n + m);
	memcpy(p, q, sizeof(p));
	for (register int i = 1;i <= n + m;i++) p[i].x = 1000002 - p[i].x, p[i].y = 1000002 - p[i].y;
	cdq1(1, n + m);
}

int main() {
	Read();
	memset(ans, 0x3f, sizeof(ans));
	
	// for (register int i = 1;i <= m;i++) {
	// 	if (ans[i] != 0x3f3f3f3f) printf("%d\n", ans[i]);
	// }
	
	// for (register int i = 1;i <= n + m;i++) {
	// 	printf("%d %d %d %d\n", p[i].type, p[i]._time, p[i].x, p[i].y);
	// }
	Solve();
	for (register int i = 1;i <= m;i++) {
		if (ans[i] != 0x3f3f3f3f) printf("%d\n", ans[i]);
	}
	return 0;
}