#line 1 "a.cpp" #define PROBLEM "https://yukicoder.me/problems/no/2220" #line 2 "/home/kuhaku/atcoder/github/algo/lib/template/template.hpp" #pragma GCC target("sse4.2,avx2,bmi2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include template bool chmax(T &a, const U &b) { return a < (T)b ? a = (T)b, true : false; } template bool chmin(T &a, const U &b) { return (T)b < a ? a = (T)b, true : false; } constexpr std::int64_t INF = 1000000000000000003; constexpr int Inf = 1000000003; constexpr int MOD = 1000000007; constexpr int MOD_N = 998244353; constexpr double EPS = 1e-7; constexpr double PI = M_PI; #line 3 "/home/kuhaku/atcoder/github/algo/lib/math/pow.hpp" std::int64_t safe_mod(std::int64_t a, std::int64_t mod) { a %= mod; return a >= 0 ? a : a + mod; } std::int64_t pow_int(std::int64_t a, std::int64_t n) { assert(n >= 0); std::int64_t res = 1, mul = a; for (; n > 0; n >>= 1) { if (n & 1) res *= mul; mul *= mul; } return res; } std::int64_t inv_mod(std::int64_t a, std::int64_t mod) { std::int64_t b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; std::swap(a -= t * b, b); std::swap(u -= t * v, v); } return u >= 0 ? u % mod : (mod - (-u) % mod) % mod; } std::int64_t pow_mod(std::int64_t a, std::int64_t n, std::int64_t mod) { if (n < 0) return inv_mod(pow_mod(a, -n, mod), mod); std::int64_t res = 1, mul = safe_mod(a, mod); for (; n > 0; n >>= 1) { if (n & 1) (res *= mul) %= mod; (mul *= mul) %= mod; } return res; } int ceil_pow2(std::int64_t n) { int x = 0; while ((std::uint64_t(1) << x) < (std::uint64_t)(n)) ++x; return x; } int floor_pow2(std::int64_t n) { int x = 0; while ((std::uint64_t(1) << (x + 1)) <= (std::uint64_t)(n)) ++x; return x; } #line 3 "/home/kuhaku/atcoder/github/algo/lib/segment_tree/monoid.hpp" template struct Add { using value_type = T; static constexpr T id = T(0); static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; } template static constexpr U f(T lhs, U rhs) { return lhs + rhs; } }; template struct And { using value_type = T; static constexpr T id = std::numeric_limits::max(); static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; } template static constexpr U f(T lhs, U rhs) { return lhs & rhs; } }; template struct Or { using value_type = T; static constexpr T id = T(0); static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; } template static constexpr U f(T lhs, U rhs) { return lhs | rhs; } }; template struct Xor { using value_type = T; static constexpr T id = T(0); static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; } template static constexpr U f(T lhs, U rhs) { return lhs ^ rhs; } }; template struct Min { using value_type = T; static constexpr T id = std::numeric_limits::max(); static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); } template static constexpr U f(T lhs, U rhs) { return std::min((U)lhs, rhs); } }; template struct Max { using value_type = T; static constexpr T id = std::numeric_limits::min(); static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); } template static constexpr U f(T lhs, U rhs) { return std::max((U)lhs, rhs); } }; template struct Update { using value_type = T; static constexpr T id = std::numeric_limits::max(); static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id ? rhs : lhs; } template static constexpr U f(T lhs, U rhs) { return lhs == Update::id ? rhs : lhs; } }; template struct Affine { using value_type = std::pair; static constexpr std::pair id = std::pair(1, 0); static constexpr std::pair op(std::pair lhs, std::pair rhs) { return {lhs.first * rhs.first, lhs.first * rhs.second + lhs.second}; } }; template struct Rev { using T = typename M::value_type; using value_type = T; static constexpr T id = M::id; static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); } }; #line 4 "/home/kuhaku/atcoder/github/algo/lib/segment_tree/dual_segment_tree.hpp" /** * @brief 双対セグメント木 * * @tparam M */ template struct dual_segment_tree { using T = typename M::value_type; dual_segment_tree(int _n, T _e = M::id) { this->init(_n, _e); } void init(int n, T e) { this->_log = ceil_pow2(n); this->_size = 1 << this->_log; this->data.assign(this->_size << 1, e); } T at(int k) { return this->get(k); } T get(int k) { assert(0 <= k && k < this->_size); k += this->_size; for (int i = this->_log; i >= 1; --i) this->push(k >> i); return this->data[k]; } void apply(int a, T val) { this->apply(a, a + 1, val); } void apply(int a, int b, T val) { assert(0 <= a && a <= this->_size); assert(0 <= b && b <= this->_size); a += this->_size, b += this->_size; for (int i = _log; i >= 1; --i) { if (((a >> i) << i) != a) this->push(a >> i); if (((b >> i) << i) != b) this->push((b - 1) >> i); } for (; a < b; a >>= 1, b >>= 1) { if (a & 1) this->all_apply(a++, val); if (b & 1) this->all_apply(--b, val); } } private: int _size, _log; std::vector data; void all_apply(int k, T val) { this->data[k] = M::op(val, this->data[k]); } void push(int k) { this->all_apply(2 * k, this->data[k]); this->all_apply(2 * k + 1, this->data[k]); this->data[k] = M::id; } }; #line 3 "/home/kuhaku/atcoder/github/algo/lib/template/macro.hpp" #define FOR(i, m, n) for (int i = (m); i < int(n); ++i) #define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i) #define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i) #define rep(i, n) FOR (i, 0, n) #define repn(i, n) FOR (i, 1, n + 1) #define repr(i, n) FORR (i, n, 0) #define repnr(i, n) FORR (i, n + 1, 1) #define all(s) (s).begin(), (s).end() #line 3 "/home/kuhaku/atcoder/github/algo/lib/template/sonic.hpp" struct Sonic { Sonic() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } constexpr void operator()() const {} } sonic; #line 5 "/home/kuhaku/atcoder/github/algo/lib/template/atcoder.hpp" using namespace std; using ll = std::int64_t; using ld = long double; template std::istream &operator>>(std::istream &is, std::pair &p) { return is >> p.first >> p.second; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &i : v) is >> i; return is; } template std::ostream &operator<<(std::ostream &os, const std::pair &p) { return os << '(' << p.first << ',' << p.second << ')'; } template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (auto it = v.begin(); it != v.end(); ++it) { os << (it == v.begin() ? "" : " ") << *it; } return os; } template void co(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cout << head << '\n'; else std::cout << head << ' ', co(std::forward(tail)...); } template void ce(Head &&head, Tail &&...tail) { if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n'; else std::cerr << head << ' ', ce(std::forward(tail)...); } template auto make_vector(T x, int arg, Args... args) { if constexpr (sizeof...(args) == 0) return std::vector(arg, x); else return std::vector(arg, make_vector(x, args...)); } void setp(int n) { std::cout << std::fixed << std::setprecision(n); } void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes" : "No") << '\n'; } void No(bool is_not_correct = true) { Yes(!is_not_correct); } void YES(bool is_correct = true) { std::cout << (is_correct ? "YES" : "NO") << '\n'; } void NO(bool is_not_correct = true) { YES(!is_not_correct); } void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; } void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); } #line 4 "a.cpp" struct Monoid { using T = std::pair; using value_type = T; static constexpr T id = T(-1, -1); static constexpr T op(const T &lhs, const T &rhs) { if (rhs == id) return lhs; if (lhs == id) return rhs; if (rhs.second >= lhs.first) return {rhs.first, lhs.second}; return rhs; } }; int main(void) { int n; cin >> n; vector> t(n); for (auto &[x, y, z] : t) cin >> x >> y >> z; int q; cin >> q; vector x(q); cin >> x; dual_segment_tree st(q); rep (i, q) st.apply(i, {0, 1}); sort(all(t), [](auto l, auto r) { return get<2>(l) < get<2>(r); }); for (auto [l, r, a] : t) { int f = lower_bound(all(x), l) - x.begin(); int g = upper_bound(all(x), r) - x.begin(); st.apply(f, g, {a + 1, a + 2}); } rep (i, q) { if (st.get(i).first == 0) co(st.get(i).second - 1); else co(0); } return 0; }