Shared code

// add me on genshin impact! 607984574
// Problem: Nearest Campsites II
// Attempted: 2025-07-30 07:35:35 EST

#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 0
#else
#include "/Users/envyaims/Documents/template/debug.cpp"
#endif
using namespace std;
using ll = long long;

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define pq priority_queue
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FORE(i,a,b) for(int i = (a); i <= (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)
#define sz(x) (int)x.size()
#define make_unique(v) v.erase(unique(all(v)), v.end());
 
template<class T> using minpq = pq<T, vector<T>, greater<T>>;
template<class T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
template<int D, typename T>struct vt : public vector<vt<D - 1, T>> { template<typename... Args>
	vt(int n = 0, Args... args) : vector<vt<D - 1, T>>(n, vt<D - 1, T>(args...)) {}};
template<typename T> struct vt<1, T> : public vector<T> {
	vt(int n = 0, const T& val = T()) : vector<T>(n, val) {}};
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

template<typename T>
struct compress{
	vector<T> v;
	int n;
	compress(vector<T> _v){
		v = _v;
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		n = v.size();
	}
	int operator()(T x){
		auto it = lower_bound(v.begin(), v.end(), x);
		assert(it != v.end() && *it == x);
		return it - v.begin();
	}
	T inv(int x){
		assert(x >= 0 && x < n);
		return v[x];
	}
};

struct segtree{
	using item = int;
	item merge(item a, item b){
		return min(a, b);
	}
	item NEUTRAL = 1e9;
	int n;
	vector<item> seg;
	segtree(int n){
		this->n = n;
		seg.resize(2 * n, NEUTRAL);
	}
	void update(int idx, int x){
		idx += n;
		seg[idx] = x;
		while(idx /= 2){
			seg[idx] = merge(seg[2 * idx], seg[2 * idx + 1]);
		}
	}
	item query(int l, int r){
		if(l > r) return NEUTRAL;
		item L = NEUTRAL, R = NEUTRAL;
		for(l += n, r += n + 1; l < r; l /= 2, r /= 2){
			if(l % 2 == 1){
				L = merge(L, seg[l++]);
			}
			if(r % 2 == 1){
				R = merge(seg[--r], R);
			}
		}
		return merge(L, R);
	}
};

struct Event{
	int x, y, type, upd, idx;
};

void uwu(){
	int n, m; cin >> n >> m;
	vector<pair<int, int>> a(n), b(m);
	trav(i, a) cin >> i.F >> i.S;
	trav(i, b) cin >> i.F >> i.S;
	vector<int> relevant_y;
	FOR(i,0,n) relevant_y.pb(a[i].S);
	FOR(i,0,m) relevant_y.pb(b[i].S);
	compress<int> comp(relevant_y);
	vector<int> ans(m, 1e9);
	
	// case 1: x_reserved >= x_free && y_reserved >= y_free
	// dist = (x_reserved + y_reserved) - (x_free + y_free)
	{
		vector<Event> events;
		FOR(i,0,n){
			events.pb({a[i].F, a[i].S, 0, a[i].F + a[i].S, -1});
		}
		FOR(i,0,m){
			events.pb({b[i].F, b[i].S, 1, b[i].F + b[i].S, i});
		}
		sort(all(events), [&](Event A, Event B){
			if(A.x != B.x) return A.x > B.x;
			return A.type < B.type; // process updates before queries if equal
		});
		segtree st(comp.n);
		trav(ev, events){
			if(ev.type == 0){
				st.update(comp(ev.y), ev.upd);
			}
			else{
				// get the min value with y_reserved greater than y_free
				int res = st.query(comp(ev.y), comp.n - 1);
				ckmin(ans[ev.idx], res - ev.upd);
			}
		}
	}
	
	// case 2: x_reserved >= x_free && y_reserved <= y_free
	// dist = (x_reserved - y_reserved) - (x_free - y_free)
	{
		vector<Event> events;
		FOR(i,0,n){
			events.pb({a[i].F, a[i].S, 0, a[i].F - a[i].S, -1});
		}
		FOR(i,0,m){
			events.pb({b[i].F, b[i].S, 1, b[i].F - b[i].S, i});
		}
		sort(all(events), [&](Event A, Event B){
			if(A.x != B.x) return A.x > B.x;
			return A.type < B.type; // process updates before queries if equal
		});
		segtree st(comp.n);
		trav(ev, events){
			if(ev.type == 0){
				st.update(comp(ev.y), ev.upd);
			}
			else{
				// get the min value with y_reserved smaller than y_free
				int res = st.query(0, comp(ev.y));
				ckmin(ans[ev.idx], res - ev.upd);
			}
		}
	}
	
	// case 3: x_reserved <= x_free && y_reserved >= y_free
	// dist = (-x_reserved + y_reserved) - (-x_free + y_free)
	{
		vector<Event> events;
		FOR(i,0,n){
			events.pb({a[i].F, a[i].S, 0, -a[i].F + a[i].S, -1});
		}
		FOR(i,0,m){
			events.pb({b[i].F, b[i].S, 1, -b[i].F + b[i].S, i});
		}
		// sort by inc now
		sort(all(events), [&](Event A, Event B){
			if(A.x != B.x) return A.x < B.x;
			return A.type < B.type; // process updates before queries if equal
		});
		segtree st(comp.n);
		trav(ev, events){
			if(ev.type == 0){
				st.update(comp(ev.y), ev.upd);
			}
			else{
				// get the min value with y_reserved greater than y_free
				int res = st.query(comp(ev.y) + 1, comp.n - 1);
				ckmin(ans[ev.idx], res - ev.upd);
			}
		}
	}
	
	// case 4: x_reserved <= x_free && y_reserved <= y_free
	// dist = (-x_reserved - y_reserved) - (-x_free - y_free)
	
	{
		vector<Event> events;
		FOR(i,0,n){
			events.pb({a[i].F, a[i].S, 0, -a[i].F - a[i].S, -1});
		}
		FOR(i,0,m){
			events.pb({b[i].F, b[i].S, 1, -b[i].F - b[i].S, i});
		}
		// sort by inc now
		sort(all(events), [&](Event A, Event B){
			if(A.x != B.x) return A.x < B.x;
			return A.type < B.type; // process updates before queries if equal
		});
		segtree st(comp.n);
		trav(ev, events){
			if(ev.type == 0){
				st.update(comp(ev.y), ev.upd);
			}
			else{
				// get the min value with y_reserved smaller than y_free
				int res = st.query(0, comp(ev.y));
				ckmin(ans[ev.idx], res - ev.upd);
			}
		}
	}
	
	cout << ans << " ";
}

signed main(){
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	// cin>>t;
	while(t--){
		uwu();
	}
}