#include #include #include using namespace std; #define int long long // Range Sum Query and Range Add Query template struct LazySegmentTree { const T DEFULT_VAL = 0; vector dat; vector lazy; int end; LazySegmentTree(vector& d) { int n = d.size(); end = 1; while (end < n) end *= 2; dat.resize(2 * end - 1, DEFULT_VAL); lazy.resize(2 * end - 1, 0); for (int i = 0; i < d.size(); i++) { dat[i + end - 1] = d[i]; } for (int i = end - 2; i >= 0; i--) { dat[i] = dat[2 * i + 1] + dat[2 * i + 2]; } } void inline eval(int id, int node_lb, int node_ub) { if (lazy[id] != 0) { // 伝搬するべき値がある dat[id] += lazy[id]; if (node_ub - node_lb > 1) { lazy[2 * id + 1] += lazy[id] / 2; lazy[2 * id + 2] += lazy[id] / 2; } lazy[id] = 0; } } void inline add(int lb, int ub, T a) { add(lb, ub, a, 0, 0, end); } void inline add(int lb, int ub, T a, int id, int node_lb, int node_ub) { eval(id, node_lb, node_ub); if (node_ub <= lb || ub <= node_lb) { return; } if (lb <= node_lb && node_ub <= ub) { lazy[id] += (node_ub - node_lb) * a; eval(id, node_lb, node_ub); } else { add(lb, ub, a, id * 2 + 1, node_lb, (node_lb + node_ub) / 2); add(lb, ub, a, id * 2 + 2, (node_lb + node_ub) / 2, node_ub); dat[id] = dat[2 * id + 1] + dat[2 * id + 2]; } } T inline query(int idx) { return query(idx, idx + 1); } T inline query(int lb, int ub) { return query(lb, ub, 0, 0, end); } T inline query(int lb, int ub, int id, int node_lb, int node_ub) { eval(id, node_lb, node_ub); if (node_ub <= lb || ub <= node_lb) { return DEFULT_VAL; } if (lb <= node_lb && node_ub <= ub) { return dat[id]; } else { T vl = query(lb, ub, id * 2 + 1, node_lb, (node_lb + node_ub) / 2), vr = query(lb, ub, id * 2 + 2, (node_lb + node_ub) / 2, node_ub); return vl + vr; } } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int n, w, h; cin >> n >> w >> h; vector a(n), b(n), x(n); for (int i = 0; i < n; i++) { cin >> a[i] >> b[i] >> x[i]; x[i]--; } vector ng(w), ok(w); // 各x_iごとに得点が得られたクエリ番号を二分探索 vector id(w); for (int i = 0; i < w; i++) { ng[i] = -1; ok[i] = n + 1; id[i] = i; } // 並列二分探索 for (int loop = 0; loop < 20; loop++) { sort(id.begin(), id.end(), [&](int i, int j) { return (ng[i] + ok[i]) / 2 < (ng[j] + ok[j]) / 2; }); vector blocks(w, 0); LazySegmentTree segtree(blocks); int ptr = 0; for (int i : id) { int mid = (ng[i] + ok[i]) / 2; while (ptr <= min(n - 1, mid)) { segtree.add(x[ptr], x[ptr] + a[ptr], b[ptr]); ptr++; } if (segtree.query(i) >= h) ok[i] = mid; else ng[i] = mid; } } int A = 0; int B = 0; for (int i = 0; i < w; i++) { if (ok[i] > n) continue; if (ok[i] % 2 == 0) A++; else B++; } if (A > B) cout << "A" << endl; else if (A == B) cout << "DRAW" << endl; else cout << "B" << endl; return 0; }