// Problem: No.2220 Range Insert & Point Mex // Contest: yukicoder // URL: https://yukicoder.me/problems/no/2220 // Memory Limit: 512 MB // Time Limit: 2000 ms #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define dbg(x) cout << #x << " = " << (x) << "\n"; #define popcount(x) __builtin_popcountll((x)) #define all(v) (v).begin(), (v).end() #define pb emplace_back #define x first #define y second using namespace std; typedef long long ll; typedef pair pll; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; struct BIT { int sz; vector bit; int lowbit(int x) { return x & -x; } void add(int x, ll v) { for (int i = ++x; i <= sz; i += lowbit(i)) { bit[i] += v; } } ll ask(int x) { if (x < 0) return 0; ll ret = 0; for (int i = ++x; i >= 1; i -= lowbit(i)) { ret += bit[i]; } return ret; } void build(int _n) { sz = _n; bit = vector(sz + 10, 0); } }bit; const int N = 2e5 + 7; int n, q; int ans[N]; vector in[N], out[N]; vector v, vv; int get(int x) { return lower_bound(all(v), x) - v.begin() + 1; } int g(int x) { return lower_bound(all(vv), x) - vv.begin(); } void solve() { cin >> n; vector> a(n); for (int i = 0; i < n; i++) { for (int j = 0; j < 3; j++) { cin >> a[i][j]; } v.pb(a[i][0]); v.pb(a[i][1]); } cin >> q; vector Q(q); for (int &i : Q) { cin >> i; v.pb(i); } v.pb(INT_MAX); sort(all(v)); v.erase(unique(all(v)), v.end()); map cnt; for (auto &[l, r, x] : a) { int nl = get(l), nr = get(r + 1); in[nl].pb(x); out[nr].pb(x); vv.pb(x); } vv.pb(0); sort(all(vv)); vv.erase(unique(all(vv)), vv.end()); bit.build(vv.size() + 1); for (int i = 1; i <= v.size(); i++) { for (auto &it : in[i]) { if (++cnt[it] == 1) { bit.add(g(it), 1); } } for (auto &it : out[i]) { if (--cnt[it] == 0) { bit.add(g(it), -1); } } int l = 0, r = vv.size() + 1; while (l < r) { int mid = l + r + 1 >> 1; if (bit.ask(mid) == mid + 1) l = mid; else r = mid - 1; } if (bit.ask(l) == l + 1) ++l; ans[i] = l; if (l == 1) dbg(i); } for (int &i : Q) { cout << ans[get(i)] << "\n"; } } int main() { fastio; // freopen("input.txt", "r", stdin); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }