#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define mt make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)< pii; typedef vector vi; typedef vector vll; template struct BinaryIndexedTree { int n; vector t; BinaryIndexedTree() {} BinaryIndexedTree(int _n) :n(_n + 1), t(_n + 1) {} void add(int k, Val val) { k++; while (k < n) { t[k] += val; k += (k&-k); } } void set(int k, Val val) { add(k, -sum(k, k + 1)); add(k, val); } Val sum(int k) { Val r = 0; while (k > 0) { r += t[k]; k -= (k&-k); } return r; } Val sum(int l, int r) { return sum(r) - sum(l); } }; template struct SegmentSum { SegmentSum() {} SegmentSum(int n) : bit0(n), bit1(n) {} /* [l, r)にvalを加える */ void add(int l, int r, Val val) { bit0.add(l, val*(-l)); bit0.add(r, val*r); bit1.add(l, val); bit1.add(r, val*(-1)); } /* [l, r)の和を求める */ Val sum(int l, int r) { Val sumr = bit0.sum(r) + bit1.sum(r)*r; Val suml = bit0.sum(l) + bit1.sum(l)*l; return sumr - suml; } BinaryIndexedTree bit0, bit1; }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, w; ll h; cin >> n >> w >> h; int A = 0, B = 0; const ll MI = (ll)1e15 * (-1); // バケツ vector > u(w + 1); rep(i, n) { int a, b, x; cin >> a >> b >> x; --x; u[x].emplace_back(b, i); u[x + a].emplace_back(-b, i); } /* (時間)<=>(x座標) 入れ替える */ SegmentSum ss(n); int wl = 0; rep(x, w) { /* 今のx座標について f[i]=ss.sum(i,i+1)は 時刻iにおけるブロックの増加を表す。 なので、累積和ss.sum(0, t+1)は時刻tにおけるブロックの数(高さ)を表す。 よって、now>=ss.sum(0, t+1)を満たす最小のtがブロックの高さがh以上に達した時刻。 これのパリティを見ればいい。 */ each(p, u[x]) { int ad, now; tie(ad, now) = p; /* ad>0: ブロックの左端がxなので、今のx座標からこのブロックを和に含める。 ad<0: ブロックの右端がx-1なので、今のx座標からこのブロックを和から取り除く。 */ ss.add(now, now + 1, ad); } int lb = 0, ub = n, mi; while (ub - lb > 1) { mi = (ub + lb) / 2; ll height = ss.sum(0, mi); (height >= h ? ub : lb) = mi; } wl += ub & 1 ? 1 : -1; } cout << (wl > 0 ? "A" : wl < 0 ? "B" : "DRAW"); }