#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl #define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i) template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template ostream& operator << (ostream &s, pair P) { return s << '<' << P.first << ", " << P.second << '>'; } template ostream& operator << (ostream &s, vector P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, vector > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template ostream& operator << (ostream &s, map P) { EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; } const int MAX = 110000; const long long INF = 1LL<<59; const int MAX_N = MAX; typedef long long VAL; // MAX typedef long long DELAY; // add const VAL UNITY_VAL = -INF; const DELAY UNITY_DELAY = 0; int SIZE_SEG; struct SegTree { pair val[4*MAX_N]; // min DELAY delay[4*MAX_N]; // + void init(int n = MAX_N, VAL v = UNITY_VAL, DELAY dv = UNITY_DELAY) { SIZE_SEG = 1; while (SIZE_SEG < n) SIZE_SEG *= 2; for (int i = 0; i < 2*SIZE_SEG-1; ++i) val[i] = make_pair(v, -1), delay[i] = dv; } inline void init_set(int a, VAL x) { int k = a + SIZE_SEG-1; val[k] = make_pair(x, a); } inline void init_tree(int k = 0, int l = 0, int r = SIZE_SEG) { if (r - l == 1) {} // leaf else { init_tree(k*2+1, l, (l+r)/2); init_tree(k*2+2, (l+r)/2, r); val[k] = merge(val[k*2+1], val[k*2+2]); } } inline pair merge(pair a, pair b) { pair res = make_pair(UNITY_VAL, -1); chmax(res, a); chmax(res, b); // res.f = a.f + b.f; return res; } inline void add(DELAY &d, DELAY x) { d += x; // d.f += x.f; } inline void reflect(pair &a, DELAY d, int l, int r) { a.first += d; // a.f += d.f * (r-l); } inline void redelay(int k, int l, int r) { reflect(val[k], delay[k], l, r); if (k < SIZE_SEG-1) { add(delay[k*2+1], delay[k]); add(delay[k*2+2], delay[k]); } delay[k] = UNITY_DELAY; } inline void renode(int k, int l, int r) { val[k] = merge(val[k*2+1], val[k*2+2]); } inline void set(int a, int b, DELAY x, int k = 0, int l = 0, int r = SIZE_SEG) { if (a <= l && r <= b) { // included add(delay[k], x); redelay(k, l, r); } else if (a < r && l < b) { // intersected redelay(k, l, r); set(a, b, x, k*2+1, l, (l+r)/2); set(a, b, x, k*2+2, (l+r)/2, r); renode(k, l, r); } else { // no-intersected redelay(k, l, r); } } inline pair get(int a, int b, int k = 0, int l = 0, int r = SIZE_SEG) { redelay(k, l, r); if (a <= l && r <= b) { // included return val[k]; } else if (a < r && l < b) { // intersected pair t1 = get(a, b, k*2+1, l, (l+r)/2); pair t2 = get(a, b, k*2+2, (l+r)/2, r); renode(k, l, r); return merge(t1, t2); } else { // no-intersected return make_pair(UNITY_VAL, -1); } } inline pair operator [] (int i) {return get(i, i+1);} void print(long long r = SIZE_SEG) { long long t = 2; for (int i = 0; i < r*2-1; ++i) { cout << make_pair(val[i], delay[i]) << ","; if (i == t-2) {cout << endl; t *= 2;} } for (int i = 0; i < r; ++i) { cout << get(i, i+1) << ", "; } cout << endl << endl; } } seg; int N, W; long long H; int main() { while (cin >> N >> W >> H) { seg.init(W + 5); for (int i = 0; i < W; ++i) seg.init_set(i, 0); seg.init_tree(); int res = 0; for (int i = 0; i < N; ++i) { int a, b, x; scanf("%d %d %d", &a, &b, &x); --x; int left = x, right = x + a; long long add = b; seg.set(left, right, add); while (true) { pair p = seg.get(0, W); //COUT(i); seg.print(); COUT(p); cout << endl << endl; if (p.first < H) break; if (i % 2 == 0) ++res; seg.set(p.second, p.second + 1, -INF); } } if (res > W-res) puts("A"); else if (res < W-res) puts("B"); else puts("DRAW"); } }