#include #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; template ostream& operator<<(ostream& os, const vector& v) { os << "sz:" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template vector Vec(int n, T v) { return vector(n, v); } template auto Vec(int n, Args... args) { auto val = Vec(args...); return vector(n, move(val)); } template constexpr T INF = numeric_limits::max() / 10; template class SegmentTree { public: using BaseAlgebra = Base; using AccMonoid = typename BaseAlgebra::AccMonoid; using OpMonoid = typename BaseAlgebra::OpMonoid; using T = typename BaseAlgebra::T; using F = typename BaseAlgebra::OpMonoid::T; SegmentTree(const int n) : data_num(n), size(1 << (1 + __lg(2 * data_num - 1))), half(size >> 1), value(size, AccMonoid::identity()), action(size, OpMonoid::identity()) { assert(n > 0); } SegmentTree(const std::vector& val) : data_num(val.size()), size(1 << (1 + __lg(2 * data_num - 1))), half(size >> 1), value(size), action(size, OpMonoid::identity()) { for (int data = 0; data < half; data++) { if (data < data_num) { value[data + half] = val[data]; } else { value[data + half] = AccMonoid::identity(); } } for (int node = half - 1; node >= 1; node--) { value[node] = acc(value[2 * node], value[2 * node + 1]); } } void initialize() { for (int i = 0; i < size; i++) { value[i] = AccMonoid::identity(); action[i] = OpMonoid::identity(); } } void initialize(const vector& val) { for (int data = 0; data < half; data++) { if (data < data_num) { value[data + half] = val[data]; } else { value[data + half] = AccMonoid::identity(); } } for (int node = half - 1; node >= 1; node--) { value[node] = acc(value[2 * node], value[2 * node + 1]); } } T get(const int a) const { assert(0 <= a and a < data_num); return accumulate(a, a + 1); } void set(const int a, const T& val) { assert(0 <= a and a < data_num); const int node = a + half; value[node] = val; for (int i = node / 2; i > 0; i /= 2) { value[i] = acc(value[2 * i], value[2 * i + 1]); } } T accumulate(const int a, const int b) const // Accumulate (a,b] { assert(0 <= a and a < b and b <= data_num); return accumulateRec(1, 0, half, a, b); } void modify(const int a, const int b, const F& f) // Apply f on (a,b] { assert(0 <= a and a < b and b <= data_num); if (f == OpMonoid::identity()) { return; } modifyRec(1, 0, half, a, b, f); } int query(const int a, const int b) const // query (a,b] { assert(0 <= a and a < b and b <= data_num); return queryRec(1, 0, half, a, b); } private: void modifyRec(const int range_index, const int range_left, const int range_right, const int op_left, const int op_right, const F& f) { if (op_left <= range_left and range_right <= op_right) { value[range_index] = act(f, value[range_index]); action[range_index] = compose(f, action[range_index]); } else if (range_right <= op_left or op_right <= range_left) { // Do nothing } else { modifyRec(2 * range_index, range_left, (range_left + range_right) / 2, 0, half, action[range_index]); modifyRec(2 * range_index, range_left, (range_left + range_right) / 2, op_left, op_right, f); modifyRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, 0, half, action[range_index]); modifyRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, op_left, op_right, f); value[range_index] = acc(value[2 * range_index], value[2 * range_index + 1]); action[range_index] = OpMonoid::identity(); } } T accumulateRec(const int range_index, const int range_left, const int range_right, const int op_left, const int op_right) const { if (op_left <= range_left and range_right <= op_right) { return value[range_index]; } else if (range_right <= op_left or op_right <= range_left) { return AccMonoid::identity(); } else { return act(action[range_index], acc(accumulateRec(2 * range_index, range_left, (range_left + range_right) / 2, op_left, op_right), accumulateRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, op_left, op_right))); } } int queryRec(const int range_index, const int range_left, const int range_right, const int op_left, const int op_right) const { if (op_left <= range_left and range_right <= op_right) { return value[range_index]; } else if (range_right <= op_left or op_right <= range_left) { return AccMonoid::identity(); } else { return queryRec(2 * range_index, range_left, (range_left + range_right) / 2, op_left, op_right) + queryRec(2 * range_index + 1, (range_left + range_right) / 2, range_right, op_left, op_right); } } const int data_num; // Num of valid data on leaves. const int size; const int half; vector value; // Tree for value(length: size) vector action; // Tree for action(length: half) bool has_lazy; const AccMonoid acc{}; const OpMonoid compose{}; const BaseAlgebra act{}; }; struct Sum_Plus { using T = ll; struct AccMonoid { T operator()(const T& a, const T& b) const { return a + b; } static constexpr T identity() { return 0; } }; struct OpMonoid { using T = ll; T operator()(const T& f1, const T& f2) const { return f1 + f2; } static constexpr T identity() { return 0; } }; T operator()(const OpMonoid::T& f, const T& x) const { return f + x; } }; template void ParallelBinarySearch(const vector& queries, Checker& checker, const int inf, const int sup, vector& ans) { const int Q = queries.size(); ans.resize(Q, INF); using Query = pair; struct Qset { int l; int r; vector query; }; vector data{Qset{inf, sup, vector(Q)}}; for (int i = 0; i < Q; i++) { data[0].query[i] = make_pair(queries[i], i); } for (int d = 0;; d++) { if (data.empty()) { break; } vector next; checker.initialize(); int pos = 0; for (const auto& dat : data) { const int inf = dat.l; const int sup = dat.r; const int mid = (inf + sup) / 2; Qset former{inf, mid, vector{}}; Qset latter{mid + 1, sup, vector{}}; for (; pos < mid; pos++) { checker.update(pos); } if (inf >= sup - 1) { for (const auto& e : dat.query) { if (checker.check(e.first)) { ans[e.second] = inf; } else if (inf == sup - 1) { latter.query.push_back(e); } } } else { for (const auto& e : dat.query) { if (checker.check(e.first)) { former.query.push_back(e); } else { latter.query.push_back(e); } } } if (not former.query.empty()) { next.push_back(former); } if (not latter.query.empty()) { next.push_back(latter); } } data = next; } } using Data = int; struct Op { ll a; ll b; ll x; }; vector op; int N; ll H; ll W; // Checker::initialize() => void // Checker::update(int pos) => void // Checker::check(const Data&) => bool struct Checker { Checker() : seg(W) {} void initialize() { seg.initialize(); } void update(const int pos) { const auto& q = op[pos]; const ll l = q.x; const ll r = q.a + q.x; seg.modify(l, r, q.b); } bool check(const Data& data) { return seg.get(data) >= H; } SegmentTree seg; }; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; cin >> W >> H; vector queries(W); for (int i = 0; i < W; i++) { queries[i] = i; } for (int i = 0; i < N; i++) { ll a, b, x; cin >> a >> b >> x; x--; op.push_back(Op{a, b, x}); } Checker checker; vector ans; ParallelBinarySearch(queries, checker, 0, N, ans); ll a = 0; ll b = 0; for (int i = 0; i < W; i++) { (ans[i] % 2 == 0 ? b : a)++; } show(ans); cout << (a == b ? "DRAW" : a < b ? "B" : "A") << endl; return 0; }