시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 6 5 100.000%

문제

순서대로 나열된 n개의 수를 두고, A와 B 두 사람이 번갈아가며 진행하는 게임이 있다. 편의상 나열된 수를 순서대로 a_1, a_2, ..., a_n이라고 하자.

게임은 A부터 시작하는데, A는 a_n을 포함하여 연속된, 하나 이상의 수를 선택해 가야 한다. a_n 하나만 선택할 수도 있고, a_1부터 a_n까지 모두를 선택할 수도 있다. a_(n-2)와 a_n와 같이 수를 가져갈 수는 없다. 왜냐하면 연속되어 있지 않기 때문이다. a_(n-2)를 가져가려면 반드시 a_(n-1)과 a_n도 가져가야 하는 것이다.

A가 규칙에 따라 a_k부터 a_n까지의 수를 선택해 갔다면, B는 A와 마찬가지로 a_(k-1)을 포함한 연속된 하나 이상의 수를 선택해 간다. 이런 식으로 서로 번갈아가며 게임이 진행되고, 수가 하나도 남지 않게 되면 게임은 끝난다. A와 B 중 선택해 간 수의 합이 적은 사람이 승리하게 된다. 합이 같은 경우에는 비기는 것으로 한다.

예를 들어 n=5이고 수가 10 7 2 4 2 라고 하자. A가 2를 가져갔다. B는 2와 4를 가져갔다. A가 7을 가져갔다. B가 10을 가져가고 게임이 끝났다. A가 가져간 수의 합은 9이고 B가 가져간 수의 합은 16이 되어 A가 이기게 된다.

A와 B는 모두 게임에서 이기기 위해 최선을 다한다고 한다. n개의 수가 주어졌을 때 이 수 게임의 승자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1<=n<=3,000) 이어서 세 개의 줄에는 처음에 주어지는 n개의 정수가 각각 주어진다. 주어지는 정수의 절대값은 10,000 이하이다.

출력

첫째 줄부터 셋째 줄까지, 입력의 각 경우에 해당되는 승자(A 또는 B)를 각각 차례대로 출력한다. 비기는 경우에는 D를 출력한다. (Draw)

예제 입력

5
10 7 2 4 2
-5 1 1 1 3
1 1 1 1 0

예제 출력

A
B
D

힌트