Alice and Bob received an even length array as a gift and decided to play a simple game. Alice will pick an element from the beginning of the array, and Bob will pick an element from the end. After each turn, they remove their picked element from the array. Untill array become empty.

At the end of each round:

• If Alice's score is greater than Bob's, print "\(A\)".
• If Bob's score is greater than Alice's, print "\(B\) ".
• If their scores are the same, print "\(D\)".

Without quotation marks

The first line contains an integer \(n\) \(\)— the number of elements in the array (\(n\) always even).
The second line contains \(n\) space-separated integers \(a_1, a_2, a_3, ..., a_n\) — the elements of the array.

\(2 \leq n \leq 1000\)
\(0 \leq a_i \leq 1000\)
 

After each round, print \(A\), \(B\) or \(D\) based on the comparison of Alice's and Bob's scores. You have to print these characters space-separated.

Input copy	Output copy
6 10 20 50 50 10 100	B A D

Input copy	Output copy
6 10 20 50 50 10 10	D A D

Explanation for testcase #1

Initial array: \([10, 20, 50, 50, 10, 100]\)
Round 1: Alice picks \(10\), Bob picks \(100\). Bob's score is higher than Alice's, so the result is \(B\). The array becomes \( [20, 50, 50, 10]\).
Round 2: Alice picks \(20\), Bob picks \(10\). Alice's score is higher than Bob's, so the result is \(A\). The array becomes \([50, 50]\).
Round 3: Alice picks \(50\), Bob picks \(50\). Both scores are equal, so the result is \(D\). The array is now empty.