#include #include #include #include #include #include #include // https://yukicoder.me/problems/no/511 template constexpr T popCount(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : (T)__builtin_popcountll(u); #else unsigned long long v = static_cast(u); return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); #endif } template constexpr T log2p1(const T u) { #ifdef __has_builtin return u == 0 ? T(0) : T(64 - __builtin_clzll(u)); #else unsigned long long v = static_cast(u); return v = static_cast(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), popCount(v); #endif } template constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); } template constexpr T msbp1(const T v) { return log2p1(v); } template constexpr T lsbp1(const T v) { #ifdef __has_builtin return __builtin_ffsll(v); #else return v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1); #endif } template constexpr bool ispow2(const T v) { return popCount(v) == 1; } template constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); } //!=======================================================================!// //! dP .d88888b !// //! 88 88. "' !// //! 88 .d8888b. d888888b dP dP 'Y88888b. .d8888b. .d8888b. !// //! 88 88' '88 .d8P' 88 88 '8b 88ooood8 88' '88 !// //! 88 88. .88 .Y8P 88. .88 d8' .8P 88. ... 88. .88 !// //! 88888888P '88888P8 d888888P '8888P88 Y88888P '88888P' '8888P88 !// //! .88 .88 !// //! d8888P d8888P !// //!=======================================================================!// template class LazySeg { public: using ValMonoid = typename MAct::ValMonoid; using OpMonoid = typename MAct::OpMonoid; using T = typename ValMonoid::T; using F = typename OpMonoid::T; LazySeg(const std::size_t N, const T initial = ValMonoid::id()) : size(N), depth(clog(size)), half(1 << depth), val(half << 1, ValMonoid::id()), op(half << 1, OpMonoid::id()) { if (initial != ValMonoid::id()) { std::fill(val.begin() + half, val.end(), initial); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } } template LazySeg(const InIt first, const InIt last) : size(std::distance(first, last)), depth(clog(size)), half(1 << depth), val(half << 1, ValMonoid::id()), op(half << 1, OpMonoid::id()) { std::copy(first, last, val.begin() + half); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } T get(const std::size_t a) { return assert(a < size), fold(a, a + 1); } void set(std::size_t a, const T& v) { assert(a < size); topDown(a += half), op[a] = OpMonoid::id(), val[a] = v; while (a >>= 1) { up(a); } } T fold(std::size_t L, std::size_t R) { assert(L < R); assert(R <= size); topDown(L += half), topDown(R += half); T accl = ValMonoid::id(), accr = ValMonoid::id(); for (; L < R; L >>= 1, R >>= 1) { if (L & 1) { accl = acc(accl, val[L++]); } if (R & 1) { accr = acc(val[--R], accr); } } return acc(accl, accr); } void act(std::size_t L, std::size_t R, const F& f) { assert(L < R), assert(R <= size); const std::size_t l = L + half, r = R + half; topDown(L += half), topDown(R += half); for (std::size_t ls = 1, rs = 1; L < R; L >>= 1, R >>= 1, ls <<= 1, rs <<= 1) { if (L & 1) { update(L++, f, ls); } if (R & 1) { update(--R, f, rs); } } bottomUp(l), bottomUp(r); } void debugPrint() { std::cerr << "["; for (std::size_t i = 0; i < size; i++) { std::cerr << get(i) << (i + 1 == size ? "" : ","); } std::cerr << "]\n"; } private: void up(const std::size_t i) { val[i] = acc(val[i << 1], val[i << 1 | 1]); } void update(const std::size_t a, const F& f, const std::size_t l) { op[a] = compose(f, op[a]), val[a] = eval(f, val[a], l); } void down(const std::size_t a, const std::size_t l) { update(a << 1, op[a], l >> 1), update(a << 1 | 1, op[a], l >> 1), op[a] = OpMonoid::id(); } void topDown(const std::size_t a) { const std::size_t b = (a / (a & -a)) >> 1; for (std::size_t i = 0, l = half; i < depth; i++, l >>= 1) { const std::size_t v = a >> (depth - i); if (v > b) { break; } down(v, l); } } void bottomUp(std::size_t a) { a = (a / (a & -a)) >> 1; for (; a >= 1; a >>= 1) { up(a); } } const std::size_t size, depth, half; std::vector val; std::vector op; const ValMonoid acc{}; const OpMonoid compose{}; const MAct eval{}; }; //!===============================================================================================!// //! 888888ba 888888ba oo .d88888b dP !// //! 88 '8b 88 '8b 88. "' 88 !// //! a88aaaa8P' a88aaaa8P' dP 88d888b. 'Y88888b. .d8888b. .d8888b. 88d888b. .d8888b. 88d888b. !// //! 88 88 '8b. 88 88' '88 '8b 88ooood8 88' '88 88' '88 88' '"" 88' '88 !// //! 88 88 .88 88 88 88 d8' .8P 88. ... 88. .88 88 88. ... 88 88 !// //! dP 88888888P dP dP dP Y88888P '88888P' '88888P8 dP '88888P' dP dP !// //!===============================================================================================!// template std::vector PBinSearch(const std::size_t Q, const std::size_t N, const Init init, const Advance advance, const Check check) { struct R { std::size_t l, r; // [l,r] std::vector qs; }; std::vector Rs{{0, N + 1, std::vector(Q)}}, nRs; std::iota(Rs.back().qs.begin(), Rs.back().qs.end(), 0); std::vector ans(Q, N + 1), former, latter; nRs.reserve(Q), former.reserve(Q), latter.reserve(Q); while (not Rs.empty()) { init(); std::size_t t = 0; for (const auto& range : Rs) { const std::size_t l = range.l, r = range.r, m = (l + r) >> 1; if (l == r) { for (const std::size_t q : range.qs) { ans[q] = l; } continue; } for (; t < m; t++) { advance(t); } for (const std::size_t q : range.qs) { (check(q) ? former : latter).push_back(q); } if (not former.empty()) { nRs.push_back({l, m, former}); } if (not latter.empty()) { nRs.push_back({m + 1, r, latter}); } former.clear(), latter.clear(); } std::swap(Rs, nRs), nRs.clear(); } return ans; } //!============================!// //! 8888ba.88ba oo !// //! 88 '8b '8b !// //! 88 88 88 dP 88d888b. !// //! 88 88 88 88 88' '88 !// //! 88 88 88 88 88 88 !// //! dP dP dP dP dP dP !// //!============================!// template struct Min { using T = X; T operator()(const T& a, const T& b) const { return std::min(a, b); } static constexpr T id() { return std::numeric_limits::max(); } }; //!===================================!// //! 888888ba dP !// //! 88 '8b 88 !// //! a88aaaa8P' 88 dP dP .d8888b. !// //! 88 88 88 88 Y8ooooo. !// //! 88 88 88. .88 88 !// //! dP dP '88888P' '88888P' !// //!===================================!// template struct Plus { using T = X; T operator()(const T& a, const T& b) const { return a + b; } static constexpr T id() { return T{}; } }; //!=====================================================================!// //! 8888ba.88ba oo 888888ba dP !// //! 88 '8b '8b 88 '8b 88 !// //! 88 88 88 dP 88d888b. a88aaaa8P' 88 dP dP .d8888b. !// //! 88 88 88 88 88' '88 88888888 88 88 88 88 Y8ooooo. !// //! 88 88 88 88 88 88 88 88 88. .88 88 !// //! dP dP dP dP dP dP dP dP '88888P' '88888P' !// //!=====================================================================!// template struct Min_Plus { using ValMonoid = Min; using OpMonoid = Plus; using VT = typename ValMonoid::T; using OT = typename OpMonoid::T; template VT operator()(const OT& f, const VT& x, const Ind) const { return x == ValMonoid::id() ? x : f + x; } }; using uint = unsigned int; using ll = long long; using ull = unsigned long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::size_t N, W; ll H; std::cin >> N >> W >> H; std::vector a(N), x(N); std::vector b(N); for (std::size_t i = 0; i < N; i++) { std::cin >> a[i] >> b[i] >> x[i], x[i]--; } using Seg = LazySeg>; std::unique_ptr segptr = std::make_unique(W, 0LL); auto init = [&]() { segptr = std::make_unique(W, 0LL); }; auto advance = [&](const std::size_t t) { segptr->act(x[t], x[t] + a[t], b[t]); }; auto check = [&](const std::size_t i) { return segptr->get(i) >= H; }; const auto ans = PBinSearch(W, N, init, advance, check); ll A = 0, B = 0; for (std::size_t i = 0; i < W; i++) { (ans[i] % 2 == 1 ? A : B)++; } std::cout << (A == B ? "DRAW" : A > B ? "A" : "B") << std::endl; return 0; }