No.511 落ちゲー 〜手作業のぬくもり〜
問題文
AさんとBさんは、以下の落ちゲーを手作業で行った。このゲームでは、横幅$w$高さ無限の方眼紙を用いる。
Aさんが先手である。手番は交互に回ってくる。
(1) $i$番目の手番のプレイヤーは、$1 \times 1$ブロックを横に$a_i$個 縦に$b_i$個集めた、$a_i \times b_i$ブロックが渡される。これを好きなところに置く。
(2) 各$1\times 1$ブロックを、下がブロックか最下段になるまで、下に移動させる。
(3) ブロックの高さが新たに得点ライン$h$以上になった列の数を数える。その列の数だけ、ブロックを置いたプレイヤーは点数を得る。
(4) 全てのブロックの高さが得点ライン以上となっていれば、ゲームを終了する。なっていなければ、手番を交代し(1)に戻る。
(5) ゲームが終了した時の点数が多い方が勝ちである。
しかし、手作業でゲームを進行していたAさんとBさんは混乱して、ゲームが終了したことに気づかずに、ゲームを継続してしまった。
もちろんどちらが勝ったかもわからない。
幸いにも「$i$手目のプレイヤーは$a_i \times b_i$ブロックを$x_i$に置いた」というログが残っている。置くときはブロックの左端を$x_i$に合わせたものとする。
AさんとBさんのゲームの手順$a_i, b_i, x_i (1 \le i \leq n)$が与えられる。ゲームの結果を教えてあげてください。
入力
$n\ w\ h$ $a_1\ b_1\ x_1$ $\vdots$ $a_n\ b_n\ x_n$
$1 \leq n \leq 100000$
$1 \leq h \leq 10^{15}$
$1 \leq w \leq 100000$
$1 \leq a_i \leq w$
$1 \leq b_i \leq 10^9$
$1 \leq x_i \leq w - a_i + 1$
入力値は全て自然数である。
入力される手順を行ったあとでは、必ずゲームは終了していることが保証される。
出力
Aさんが勝つならば"A", Bさんが勝つならば"B", 引き分けなら"DRAW"と出力して下さい(""は明確化のため)。 最後に改行してください。
サンプル
サンプル1
入力
1 3 2 3 2 1
出力
A
サンプル2
入力
2 3 2 3 1 1 3 1 1
出力
B
サンプル3
入力
3 3 2 1 2 1 1 2 2 1 2 3
出力
A
サンプル4
入力
2 2 2 1 2 1 1 2 2
出力
DRAW
サンプル5
入力
9 7 10 6 5 2 6 4 2 7 5 1 7 6 1 6 2 2 5 7 2 5 2 3 7 9 1 7 7 1
出力
A
4手目で本来ゲームは終了し、A君が勝利しています。
しかし、A君とB君は混乱しているのでブロックを置き続けます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。