#include "bits/stdc++.h" #ifdef WINT_MIN #define __MAI #endif using namespace std; typedef unsigned int uint; typedef long long int ll; typedef unsigned long long int ull; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<=l;--cnt) #define BIGINT 0x7FFFFFFF #define MD 1000000007ll #define PI 3.1415926535897932384626433832795 void printbit(int u) { if (u == 0)cout << 0; else { int s = 0, k = 0; for (; 0>= 1, k++)s = (s << 1) | (u & 1); for (; 0>= 1)cout << (s & 1); } }template ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast(t).count()) namespace { std::chrono::system_clock::time_point t; void tic() { t = TIME; } void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - t)); } std::chrono::system_clock::time_point tle = TIME; #ifdef __MAI void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); } #else #define safe_tle(k) ; #endif } #ifndef __MAI namespace { class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } }; } MaiScanner scanner; #else #define scanner cin #endif template //typedef int T; class segtree { int size; public: struct VI { T val; int idx; VI(T val = 0,int idx = 0):val(val),idx(idx){} static const VI& max (const VI& a, const VI& b) { return a.val == b.val ? (a.idx < b.idx ? a : b) : (a.val >= b.val ? a : b); } static const VI& min(const VI& a, const VI& b) { return a.val == b.val ? (a.idx < b.idx ? a : b) : (a.val <= b.val ? a : b); } bool operator==(const VI& e) const { return val == e.val && idx == e.idx; } bool operator<(const VI& e) const { return (val < e.val) || (idx > e.idx); } }; private: vector mark; vector single; // max(min)遅延伝搬用 vector> addtree; // sum,lazy vector maxtree; // val,idx public: segtree(int n) { size = 8; while (size < n) size <<= 1; addtree.resize(size * 2); mark.resize(size * 2); single.resize(size * 2); maxtree.resize(size * 2); _flat(); } void _flat() { for (int i = 0; i < size; ++i) { maxtree[i + size - 1] = VI(0, i); } for (int i = size - 2; 0 <= i; --i) { int c = 2 * i + 1; maxtree[i] = maxtree[c]; } } // 区間[begin,end)に一様にvalを加算する void addvalrange(int begin, int end, T val, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return; // note:範囲外 if (begin <= rangebegin && rangeend <= end) { addtree[ptr].first += val * (rangeend - rangebegin); addtree[ptr].second += val * (rangeend - rangebegin) / 2; mark[ptr] |= 3; maxtree[ptr].val += val; single[ptr] += val; if (rangeend - rangebegin > 1) { // せっかくだから _applyDown(ptr); } return; } _applyDown(ptr); // TODO:いる? int rangemid = (rangebegin + rangeend) / 2; addvalrange(begin, end, val, ptr * 2 + 1, rangebegin, rangemid); addvalrange(begin, end, val, ptr * 2 + 2, rangemid, rangeend); addtree[ptr].first += val * (min(rangeend, end) - max(rangebegin, begin)); maxtree[ptr] = max(maxtree[ptr * 2 + 1], maxtree[ptr * 2 + 2]); // インデックスもmaxを選択する点に注意 } inline void _applyDown(int ptr) { //if (size - 1 <= ptr) return; if (mark[ptr] & 1) { mark[ptr] ^= 1; int c1 = ptr * 2 + 1; int c2 = ptr * 2 + 2; addtree[c1].first += addtree[ptr].second; addtree[c1].second += addtree[ptr].second / 2; mark[c1] |= 1; addtree[c2].first += addtree[ptr].second; addtree[c2].second += addtree[ptr].second / 2; mark[c2] |= 1; addtree[ptr].second = 0; } if (mark[ptr] & 2) { mark[ptr] ^= 2; int c1 = ptr * 2 + 1; int c2 = ptr * 2 + 2; maxtree[c1].val += single[ptr]; single[c1] += single[ptr]; mark[c1] |= 2; maxtree[c2].val += single[ptr]; single[c2] += single[ptr]; mark[c2] |= 2; single[ptr] = 0; } } inline void _downward_applyDown(int ptr1) { if (1 < ptr1) _downward_applyDown(ptr1 >> 1); _applyDown(ptr1 - 1); } T getval(int index) { T sum = 0; _downward_applyDown((index + size) >> 1); return addtree[index + size - 1].first; } T getsumrange(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return 0; // note:範囲外 if (begin <= rangebegin && rangeend <= end) return addtree[ptr].first; _applyDown(ptr); int rangemid = (rangebegin + rangeend) / 2; return getsumrange(begin, end, ptr * 2 + 1, rangebegin, rangemid) + getsumrange(begin, end, ptr * 2 + 2, rangemid, rangeend); } VI getmaxrange(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return VI(0, -1); // note:範囲外 if (begin <= rangebegin && rangeend <= end) return maxtree[ptr]; _applyDown(ptr); int rangemid = (rangebegin + rangeend) / 2; VI l = getmaxrange(begin, end, ptr * 2 + 1, rangebegin, rangemid); VI r = getmaxrange(begin, end, ptr * 2 + 2, rangemid, rangeend); if (l.idx == -1) return r; if (r.idx == -1) return l; return VI::max(l, r); // インデックスもmaxを選択する点に注意 } }; ll width, height; int m, n; int main() { int i, j, k; ll x, y, a, b; const ll smaaaaaaall = -1e99; scanner >> n >> width >> height; segtree field(width); ll score_a, score_b; score_a = score_b = 0; repeat(n) { scanner >> a >> b >> x; --x; field.addvalrange(x, x + a, b); while (true) { auto p = field.getmaxrange(x, x + a); if (p.val >= height) { if (cnt % 2 == 0) { score_a += 1; } else { score_b += 1; } field.addvalrange(p.idx, p.idx+1, smaaaaaaall); } else { break; } } } repeat(10) { cerr << field.getsumrange(cnt, cnt + 1) << " "; } cerr << endl; cerr << score_a << " " << score_b << endl; if (score_a == score_b) { cout << "DRAW" << endl; } else if (score_a < score_b) { cout << "B" << endl; } else { cout << "A" << endl; } return 0; }