#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !// //!===========================================================!// using ld = long double; using ll = long long; using ull = unsigned long long; std::mt19937 mt{std::random_device{}()}; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr T MOD = static_cast(1000000007); template constexpr F PI() { return 3.1415926535897932385; } template std::ostream& operator<<(std::ostream& os, const std::array& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::deque& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::pair& v) { return (os << "<" << v.first << "," << v.second << ">"); } template std::ostream& operator<<(std::ostream& os, const std::priority_queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.front() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::stack& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::unordered_multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } #define SHOW(...) (std::cerr << "(" << #__VA_ARGS__ << ") = ("), HogeHogeSansuu(__VA_ARGS__), std::cerr << ")" << std::endl; void HogeHogeSansuu() { ; } template void HogeHogeSansuu(const T x) { std::cerr << x; } template void HogeHogeSansuu(const T x, Args... args) { (std::cerr << x << ", "), HogeHogeSansuu(args...); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T PopCount(T v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); } template constexpr T log2p1(T v) { return v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PopCount(v); } template constexpr bool ispow2(const T v) { return (v << 1) == (T(1) << (log2p1(v))); } template constexpr T ceil2(const T v) { return ispow2(v) ? v : T(1) << log2p1(v); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : ispow2(v) ? v : 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 BaseAlgebra = Base; using ValMonoid = typename BaseAlgebra::ValMonoid; using OpMonoid = typename BaseAlgebra::OpMonoid; using T = typename BaseAlgebra::VT; using F = typename BaseAlgebra::OT; LazySeg(const std::size_t N, const T initial = ValMonoid::id()) : size(N), half(ceil2(size)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id()) { if (initial != ValMonoid::id()) { std::fill(value.begin() + half, value.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)), half(ceil2(size)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id()) { std::copy(first, last, value.begin() + half); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } T get(const std::size_t a) const { return accumulate(a, a + 1); } void set(std::size_t a, const T& val) { modify(a, a + 1, OpMonoid::id()), value[a += half] = val; while (a >>= 1) { up(a); } } T accumulate(const std::size_t L, const std::size_t R) const { auto arec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> T { if (L <= left and right <= R) { return value[index]; } else if (right <= L or R <= left) { return ValMonoid::id(); } else { return act(action[index], acc(self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right))); } }; return arec(arec, 1, 0, half); } void modify(const std::size_t L, const std::size_t R, const F& f) { auto mrec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> void { if (L <= left and right <= R) { this->update(index, f); } else if (right <= L or R <= left) { } else { this->update(index << 1, action[index]), this->update(index << 1 | 1, action[index]); self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right); this->up(index), action[index] = OpMonoid::id(); } }; mrec(mrec, 1, 0, half); } std::vector data() const { std::vector ans(size); for (std::size_t i = 0; i < size; i++) { ans[i] = get(i); } return ans; } private: void up(const std::size_t i) { value[i] = acc(value[i << 1], value[i << 1 | 1]); } void update(const std::size_t i, const F& f) { value[i] = act(f, value[i]), action[i] = compose(f, action[i]); } const std::size_t size, half; std::vector value; std::vector action; const ValMonoid acc{}; const OpMonoid compose{}; const BaseAlgebra act{}; }; template std::ostream& operator<<(std::ostream& os, const LazySeg& seg) { os << "["; for (const auto& e : seg.data()) { os << e << ","; } return (os << "]" << std::endl); } //!===============================================================================================!// //! 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 InIt first, const InIt last, const X inf, const X sup) { const std::size_t Q = (std::size_t)(std::distance(first, last)); std::vector ans(Q, sup); struct QInt { X l, r; std::vector query; }; std::vector v(Q); std::iota(v.begin(), v.end(), 0); std::vector qs{{inf, sup, v}}; while (not qs.empty()) { std::vector nqs; C checker(inf); X pos = inf; for (const auto& qint : qs) { const X l = qint.l, r = qint.r, m = (l + r) / 2; if (r - l <= 1) { for (const std::size_t q : qint.query) { ans[q] = r; } } else { QInt former{l, m, std::vector()}, latter{m, r, std::vector()}; for (; pos < m; pos++) { checker.advance(); } for (const std::size_t q : qint.query) { (checker.check(*std::next(first, q)) ? former.query : latter.query).push_back(q); } if (not former.query.empty()) { nqs.push_back(former); } if (not latter.query.empty()) { nqs.push_back(latter); } } } qs = nqs; } return ans; } //!=====================================================================!// //! 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 VT = VX; struct ValMonoid { VT operator()(const VT& a, const VT& b) const { return std::min(a, b); } static constexpr VT id() { return INF; } }; using OT = OX; struct OpMonoid { OT operator()(const OT& a, const OT& b) const { return a + b; } static constexpr OT id() { return 0; } }; VT operator()(const OT& f, const VT& x) const { return f + x; } }; int N, W; ll H; std::vector a, x; std::vector b; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N >> W >> H; a.resize(N), b.resize(N), x.resize(N); for (int i = 0; i < N; i++) { std::cin >> a[i] >> b[i] >> x[i], x[i]--; } struct Checker { Checker(int inf) : cnt(inf), seg(W, 0LL) {} void advance() { cnt++, seg.modify(x[cnt], x[cnt] + a[cnt], b[cnt]); } bool check(int ind) const { return seg.get(ind) >= H; } int cnt; LazySeg> seg; }; std::vector X(W); std::iota(X.begin(), X.end(), 0); const auto ans = PBinSearch(X.begin(), X.end(), -1, N); ll A = 0, B = 0; for (int i = 0; i < W; i++) { (ans[i] % 2 == 0 ? A : B)++; } std::cout << (A == B ? "DRAW" : A > B ? "A" : "B") << std::endl; return 0; }