题目背景

JOISC2020 Day 1 T1

由于数据点较多，本题只评测其中的部分数据。

题目描述

给定两个长度为 $2n$ 的序列 $A,B$，构造一个长度为 $2n$ 的序列 $C$ 满足以下条件：

• 对于 $1\leq i\leq 2n$，$C_i$ 只能从 $A_i$ 和 $B_i$ 中选取

• $C_i$ 从 $A_i$ 中选取的次数和从 $B_i$ 中选取的次数都恰好为 $n$。

• $C$ 为单调不降的序列。

如果满足条件的 $C$ 有多个，只需要输出一个。

输入格式

第一行一个正整数 $n$。

第二行 $2n$ 个数字，第 $i$ 个为 $A_i$。

第三行 $2n$ 个数字，第 $i$ 个为 $B_i$。

输出格式

如果无解则输出 $-1$，否则按照以下方式输出一个字符串 $s$：

对于 $1\leq i\leq 2n$，如果 $C_i$ 是从 $A_i$ 选取的则 $s_i=\texttt{A}$，否则 $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

提示

样例 1 解释

构造的 $C=[2,5,6,9,12,14]$，可以自行这是满足条件的方案。

样例 2 解释

另外有 $\texttt{AABB},\texttt{ABAB},\texttt{BABA},\texttt{BAAB},\texttt{ABBA}$ 这 $5$ 组解，输出任何一组均可。

样例 3 解释

没有满足条件的方案。

子任务

子任务	特殊性质	分数
$1$	$1\leq n\leq 2\times 10^3$	$11$
$2$	无	$89$

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5,1\leq A_i,B_i\leq 10^9$。