Problem Background

JOISC2020 Day 1 T1

Due to the large number of data points, only a portion of the data will be evaluated for this problem.

Problem Description

Given two sequences \( A \) and \( B \) each 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 from \( B_i \) must each be exactly \( n \).
• The sequence \( C \) must be non-decreasing.

If there are multiple valid sequences \( C \), output any one of them.

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 \) as follows:

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

AABABB

Input Sample #2

2
1 4 10 20
3 5 8 13

Output Sample #2

BBAA

Input Sample #3

2
3 4 5 6
10 9 8 7

Output Sample #3

-1

Input Sample #4

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

Output Sample #4

BABBABAABABA

Notes

Sample 1 Explanation

The constructed \( C = [2, 5, 6, 9, 12, 14] \), which is a valid solution.

Sample 2 Explanation

There are other valid solutions such as \(\texttt{AABB}, \texttt{ABAB}, \texttt{BABA}, \texttt{BAAB}, \texttt{ABBA}\). Any one of these can be output.

Sample 3 Explanation

There is no valid solution.

Subtasks

For \(100\%\) of the data, \(1 \leq n \leq 5 \times 10^5, 1 \leq A_i, B_i \leq 10^9\).

见题面 Input 部分

见题面 Output 部分