시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2571038047.059%

문제

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

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

A가 규칙에 따라 ak부터 an까지의 수를 선택해 갔다면, B는 A와 마찬가지로 ak-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를 출력한다.

예제 입력 1

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

예제 출력 1

A
B
D