Description

Given two sequences $A, B$ of length $2n$, construct a sequence $C$ of length $2n$ that satisfies the following conditions:

• For $1 \leq i \leq 2n$, $C_i$ can only be chosen from $A_i$ and $B_i$.

• The number of times $C_i$ is chosen from $A_i$ and the number of times it is chosen from $B_i$ are both exactly $n$.

• $C$ is a non-decreasing sequence.

If there are multiple valid sequences $C$, you only need to output one.

Input Format

The first line contains a positive integer $n$.

The second line contains $2n$ numbers, where the $i$-th number is $A_i$.

The third line contains $2n$ numbers, where the $i$-th number is $B_i$.

Output Format

If there is no solution, output $-1$. Otherwise, output a string $s$ in the following way:

For $1 \leq i \leq 2n$, if $C_i$ is chosen from $A_i$, then $s_i=\texttt{A}$; otherwise, $s_i=\texttt{B}$.

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

AABABB

2
1 4 10 20
3 5 8 13

BBAA

2
3 4 5 6
10 9 8 7

-1

6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78

BABBABAABABA

Hint

Sample 1 Explanation

The constructed $C=[2,5,6,9,12,14]$. You can check for yourself that this satisfies the conditions.

Sample 2 Explanation

There are also $5$ other solutions: $\texttt{AABB}, \texttt{ABAB}, \texttt{BABA}, \texttt{BAAB}, \texttt{ABBA}$. Any one of them is acceptable.

Sample 3 Explanation

There is no solution that satisfies the conditions.

Subtasks

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 5\times 10^5$, $1 \leq A_i, B_i \leq 10^9$.

Translated by ChatGPT 5