Number Game

There are n integers a1, a2, ..., an written in order. A and B play alternately, starting with A.

On each turn, the player must take one or more consecutive numbers that include the rightmost remaining number. If the remaining numbers are a1 through ai, the player chooses some k and takes all numbers ak, ak+1, ..., ai. Those numbers are removed, and the next turn continues with only a1 through a{k-1} remaining.

The game ends when no numbers remain. Compare the sums of the numbers taken by each player; the player with the smaller sum wins. If the sums are equal, the game is a draw.

Both players choose optimally for themselves. Write a program that determines the winner of each of the three given games.

The first line contains n. (1 <= n <= 3,000)

Each of the next three lines describes one game and contains n space-separated integers. The absolute value of each integer is at most 10,000.

Print three lines. On the i-th line, print the winner of the i-th game from the input.

Print A if A wins, B if B wins, and D if the game is a draw.