## SSEQ

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
const int N = 1e6+5;
struct vcl {
	int l,r,w;
	bool operator < (const vcl &o) const {
		return l < o.l;
	}
}a[N];
int mx = 0;
const int inf = 1e18;
struct segtri {
	int n;
	vector<int> node,lazy;
	segtri () {}
	segtri (int n) :n(n) {
		node.resize(4*n+5);
		lazy.resize(4*n+5);
	} 
	void down (int id) {
		int val = lazy[id];
		node[2*id] += val;
		node[2*id+1] += val;
		lazy[2*id] += val;
		lazy[2*id+1] += val;
		lazy[id] = 0;
	}
	void update (int id, int l, int r, int u, int v, int val) {
		if (l > v || r < u) return;
		if (l>=u&&r<=v) {
			node[id] += val;
			lazy[id] += val;
			return;
		}
		if (lazy[id]) down(id);
		int mid = (r+l) >> 1;
		update (2*id,l,mid,u,v,val);
		update (2*id+1,mid+1,r,u,v,val);
		node[id] = max (node[2*id],node[2*id+1]);
	}
	void update (int l, int r, int val) {
		update (1,1,n,l,r,val);
	}
	int get (int id, int l, int r, int u, int v) {
		if (l > v || r < u) return 0;
		if (l >= u && r <= v) return node[id];
		if (lazy[id]) down(id);
		int mid = (r+l) >> 1;
		return max (get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
	} 
	int get (int l, int r) {
		return get (1,1,n,l,r);
	}
}st;
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	mx = 0;
	for (int i=1; i<=n; i++) {
		cin >> a[i].l >> a[i].r >> a[i].w;
		mx = max (mx,a[i].r);
	}
	st = segtri(mx);
	sort (a+1,a+n+1);
	int res = -1e18;
	for (int i=n; i>=1; i--) {
		st.update (a[i].r,mx,a[i].w);
		while (i>=2&&a[i].l == a[i-1].l) {
			i--;
			st.update (a[i].r,mx,a[i].w);
		}
		res = max (res,st.get(a[i].l,mx));
	}
	cout << res;
}

## UBQ

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
const int N = 2e5+5;
int a[N];
vector<ii> vc;
vector<int> p[N];
int n,q;
void sieve () {
	int n = 2e5;
	for (int i=1; i<=n; i++) {
		for (int j=i; j<=n; j+=i) p[j].push_back(i);
	}
}
int res[N];
struct vcl {
	int val,id,sign;
};
vector<vcl> event[N];
int cnt[N];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	sieve();
	cin >> n >> q;
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		vc.push_back({a[i],i});
	}
	sort (vc.begin(),vc.end());
	for (int i=1; i<=q; i++) {
		int l,r,x; cin >> l >> r >> x;
		for (auto d : p[x]) {
			if (d == x) continue;
			res[i] += (upper_bound (vc.begin(),vc.end(),ii(d,r)) - lower_bound(vc.begin(),vc.end(),ii(d,l)));
		}
		event[l-1].push_back({x,i,-1});
		event[r].push_back({x,i,1});
	}
	for (int i=1; i<=n; i++) {
		for (auto d : p[a[i]]) cnt[d]++;
		for (auto cc : event[i]) {
			res[cc.id] += cc.sign*cnt[cc.val];
		}
	}
	for (int i=1; i<=q; i++) cout << res[i] << ' ';
}

## MRobot

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
int n;
const int N = 3e5+5;
const int inf = 4e18;
struct point {
	int x,y;
}a[N];
bool mini (int &a, int b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
bool maxi (int &a, int b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
bool check (int mid) {
	ii L,R;
	L.first = -inf;
	L.second = -inf;
	R.first = inf;
	R.second = inf;
	for (int i=1; i<=n; i++) {
		int x = a[i].x - mid;
		int y = a[i].y - mid;
		int u = a[i].x + mid;
		int v = a[i].y + mid;
		maxi (L.first,x);
		maxi (L.second,y);
		mini (R.first,u);
		mini (R.second,v);
	}
	return L.first <= R.first && L.second <= R.second;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> a[i].x >> a[i].y;
		int u = a[i].x + a[i].y;
		int v = a[i].x - a[i].y;
		a[i] = {u,v};	
	}
	int l = 0, r = 2e18, res = 0;
	while (r >= l) {
		int mid = (r+l) >> 1;
		if (check(mid)) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << res;
}