'I' の数 (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

英語の授業中に暇だった paiza 君は、N ページの教科書を使った次のようなゲームを思いつきました。

「2人のプレイヤーがそれぞれ教科書の 1 箇所を適当に掴んで、掴んだ範囲のページに含まれる 'I' の合計数が多い方が勝ち、少ない方が負け、同じだったら引き分け！」
「ただし、 N/3 ページ以上掴んだ人は反則負けで、 2 人とも反則したら引き分け！」
(ここでの N/3 は整数であるとは限りません)

審判を任されたあなたは、各ページに含まれる 'I' の数を記録しておくことで、掴んだページの両端の番号を確認するだけで、掴んだ範囲のページに含まれる 'I' の合計数を求めることができることに気付きました。

教科書のページ数 N と試合の数 K , 各ページの 'I' の数 I_1 ... I_N と、
i 番目の試合で対戦した A と B の 2 人が掴んだページの両端のページ番号 A_l_i, A_r_i , B_l_i, B_r_iが与えられるので、各試合のジャッジしてください。

入力される値

N K
A_1
...
A_N
A_l_1 A_r_1 B_l_1 B_r_1
...
A_l_K A_r_K B_l_K B_r_K

・1 行目では、教科書のページ数 N とおこなわれる試合数 K が与えられます。
・続く N 行のうち、 i 行目では、教科書の i ページ目に含まれる 'I' の数が与えられます。
・続く K 行のうち、 i 行目では、i 試合目のプレイヤー A が掴んだページの両端のページ番号 A_l_i , A_r_i とプレイヤー B が掴んだページの両端のページ番号 B_l_i , B_r_i が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

ans_1
...
ans_K

・i 行目に i 試合目の結果を出力してください。
A の勝ちの場合は 'A', B の勝ちの場合は 'B' , 引き分けの場合は 'DRAW' と出力してください。
・また、出力の末尾には改行を入れてください。

条件: ・1 ≦ N ≦ 100,000
・1 ≦ K ≦ 100,000
・0 ≦ A_i ≦ 100 (1 ≦ i ≦ N)
・1 ≦ A_l_i ≦ A_r_i ≦ N (1 ≦ i ≦ K)
・1 ≦ B_l_i ≦ B_r_i ≦ N (1 ≦ i ≦ K)

入力例1: 3 3
0
1
2
1 1 2 2
2 2 3 3
3 3 3 3

出力例1: DRAW
DRAW
DRAW

入力例2: 10 3
10
9
8
7
6
5
4
3
2
1
1 3 7 10
1 4 3 4
1 5 6 10

出力例2: A
B
DRAW

問題一覧へ戻る