問題一覧 > 通常問題

No.511 落ちゲー 〜手作業のぬくもり〜

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : はむこはむこ / テスター : りあんりあん
4 ProblemId : 1292 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-03-21 13:00:50

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。