Description

Input

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of numbers.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). Furthermore, there are no pair of indices $i \neq j$ such that $a_i = a_j$.

Output

Print $s$ — a string of $n$ characters, where the $i$-th character represents the outcome of the game if the token is initially placed in the cell $i$. If Alice wins, then $s_i$ has to be equal to "A"; otherwise, $s_i$ has to be equal to "B".

8
3 6 5 4 2 7 1 8

BAAAABAB

15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14

ABAAAABBBAABAAB

Note

In the first sample, if Bob puts the token on the number (not position):

• $1$: Alice can move to any number. She can win by picking $7$, from which Bob has no move.
• $2$: Alice can move to $3$ and $5$. Upon moving to $5$, Bob can win by moving to $8$. If she chooses $3$ instead, she wins, as Bob has only a move to $4$, from which Alice can move to $8$.
• $3$: Alice can only move to $4$, after which Bob wins by moving to $8$.
• $4$, $5$, or $6$: Alice wins by moving to $8$.
• $7$, $8$: Alice has no move, and hence she loses immediately.