#line 1 "Main.cpp" #include #include #include #include #include #line 2 "nachia\\set\\word-size-tree.hpp" #line 5 "nachia\\set\\word-size-tree.hpp" namespace nachia{ struct WordsizeTree{ using Word = unsigned long long; static constexpr int W = 64; int N; std::vector> A; static int highBit(Word x){ if(x == 0) return 0; return W-1 - __builtin_clzll(x); } static int lowBit(Word x){ if(x == 0) return W; return __builtin_ctzll(x); } WordsizeTree(unsigned int length){ N = length; int n = length; do { std::vector a(n/W+1,0); A.emplace_back(std::move(a)); n /= W; } while(n); } WordsizeTree(const std::string& binStr = ""){ N = binStr.size(); int n = N; { std::vector a(n/W+1); for(int i=0; i a(n/W+1,0); for(int i=0; i<=n; i++){ if(A.back()[i]) a[i/W] |= (Word)1 << (i%W); } A.emplace_back(std::move(a)); n /= W; } } void insert(int x){ for(auto& a : A){ a[x/W] |= (Word)1 << (x % W); x /= W; } } void erase(int x){ for(auto& a : A){ a[x/W] &= ~((Word)1 << (x % W)); if(a[x/W]) return; x /= W; } } int count(int x) const { return (int)((A[0][x/W] >> (x%W)) & 1); } int noLessThan(int x) const { int d = 0, i = x; while(true){ if(d >= (int)A.size()) return -1; if(i/W >= (int)A[d].size()) return -1; Word m = A[d][i/W] & ((~(Word)0) << (i%W)); if(!m){ d++; i /= W; i++; } else{ int to = lowBit(m); i = i/W*W + to; if(d == 0) break; i *= W; d--; } } return i; } int noGreaterThan(int x) const { int d = 0, i = x; while(true){ if(i < 0) return -1; if(d >= (int)A.size()) return -1; Word m = A[d][i/W] & ~((~(Word)1) << (i%W)); if(!m){ d++; i /= W; i--; } else{ int to = highBit(m); i = i/W*W + to; if(d == 0) break; i *= W; i += W-1; d--; } } return i; } }; } // namespace nachia #line 7 "Main.cpp" using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<1000000007>; int main(){ int N; cin >> N; vector> Ins, Rem; rep(i,N){ int l, r, a; cin >> l >> r >> a; l--; if(a > N) continue; Ins.emplace_back(l, a); Rem.emplace_back(r, a); } sort(Ins.begin(), Ins.end()); sort(Rem.begin(), Rem.end()); int Q; cin >> Q; vector T(Q); rep(i,Q) cin >> T[i]; nachia::WordsizeTree rex(string(N+1, '1')); vector cnt(N+1); int ii = 0; int ir = 0; rep(i,Q){ while(ii < (int)Ins.size() && Ins[ii].first < T[i]) if(cnt[Ins[ii++].second]++ == 0) rex.erase(Ins[ii-1].second); while(ir < (int)Rem.size() && Rem[ir].first < T[i]) if(--cnt[Rem[ir++].second] == 0) rex.insert(Rem[ir-1].second); cout << rex.noLessThan(0) << '\n'; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;