https://blog.csdn.net/tenkuo/article/details/153559955?spm=1001.2014.3001.5502

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

typedef long long LL;
#define pl pair<LL, LL>
#define ppl pair<pl, pl>
#define x first
#define y second
const int N = 3e5 + 10;

vector<pl> ti[N];   // 每个时刻新加进的线段 
multiset<LL> cont;   // 当前所有缝隙贡献 
set<ppl> bs;         // 连通块们 
LL X, Y;            // 起始结束点 

LL calc_dis(LL x, LL y) {   // 计算 floor(sqrt(z)) 
	LL z = x * x + y * y;
	LL t = sqrt(z);
	while (t * t <= z) {
		t ++;
	}
	while (t * t > z) {
		t --;
	}
	return t;
}

LL part_near(LL l, LL r, LL x) {   // 计算这个区间里离 x 最近的点 
	if (x < l) {
		return l;
	}
	else if (x > r) {
		return r;
	}
	else {
		return x;
	}
}

void deal_cont(ppl a, ppl b, int flag) {   // 处理两个连通块之间的缝隙 
	// 计算缝隙范围 
	pl l = {a.x.y, b.x.x};  // [a.max_x, b.min_x]
	pl r = {a.y.y, b.y.x};  // [a.max_y, b.min_y]
	
	LL dis_x = part_near(l.x, l.y, X); 
	LL dis_y = part_near(r.x, r.y, Y);
	LL res = abs(X - dis_x) + abs(Y - dis_y) + calc_dis(dis_x, dis_y);
	
	if (flag == 1) {
		cont.insert(res);   // 添加 
	}
	else {
		// find 返回指针 
		cont.erase(cont.find(res));    // 删除 
	}
} 

// 处理 blo 对应缝隙，flag 为 1 就是加 blo 到平面，为 0 就是删除 
void change(ppl blo, int flag) {    
	auto it = bs.find(blo);   // 在 bs 里 找到当前的连通块（返回指针） 
	if (it != bs.begin()) {   // begin 是存有实体的第一个 
		deal_cont(*prev(it), *it, flag);
	} 
	if (next(it) != bs.end()) {
		deal_cont(*it, *next(it), flag);
	}
	if (it != bs.begin() && next(it) != bs.end()) {   // 找到的左右连通块相邻 
		deal_cont(*prev(it), *next(it), -flag);
	}
} 

bool jd_ab(ppl a, ppl b) {  // 能合并输出 1，不能输出 0 
	if (a.x.y <= b.x.x && a.y.y <= b.y.x) {
		return 0;   // a.max_x ≤ b.min_x 且 a.max_y ≤ b.min_y
	}
	return 1;
}

void merge(ppl &a, ppl b) {
	a.x.x = min(a.x.x, b.x.x);
	a.x.y = max(a.x.y, b.x.y);
	a.y.x = min(a.y.x, b.y.x);
	a.y.y = max(a.y.y, b.y.y);
} 

void ins(pl line) {    // 将这条线段加到平面里 
	ppl blo = { {line.x, line.x}, {line.y, line.y} };
	// 当只有一条线段时的连通块：x 下界与上界，y 下界与上界 
	
	while(1) {   // 不断地合并 
		auto it = bs.lower_bound(blo);   // 当前连通块右边的连通块 
		if (it != bs.end() && jd_ab(blo, *it)) {   // 不是边界且可以合并 
			change(*it, -1);    // 把原来这个连通块缝隙贡献减掉 
			merge(blo, *it);    // 合并 
			bs.erase(it);       // 合并了就删掉 
			continue;
		}
		// begin 是存有实体的第一个
		if (it != bs.begin() && jd_ab(*prev(it), blo)) {   // 不是边界且可以合并 
			auto _it = prev(it);      // prev 不是持久迭代器，后续还要删除，先开一个指针存着 
			change(*_it, -1);    // 把原来这个连通块缝隙贡献减掉
			merge(blo, *_it);    // 合并 
			bs.erase(_it);       // 合并了就删掉 
			continue;
		}
		break;    // 没得合并了退出 
	} 
	
	bs.insert(blo);   // 并完了就放进去 
	change(blo, 1);  // 把缝隙加进去 
} 

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, T;
	cin >> n >> T;
	cin >> X >> Y;
	
	for (int i = 1; i <= n; i ++) {
		int t; LL x, y;
		cin >> t >> x >> y;
		ti[t].push_back({x, y});
	}
	
	ins({0, 0});    // 上下边界（保证有缝隙） 
	ins({1e9, 1e9});   // 不然会卡似 
	
	for (int i = 0; i < T; i ++) {     // 题目时间范围 
		for (auto j : ti[i]) {
			ins(j);
		}
		cout << (*cont.begin()) << "\n";   // 路程最小的那个 
	}
	
	return 0;
}