题目描述

题目译自 JOISC 2020 Day1 T1「ビルの飾り付け 4 / Building 4」

给定长度为 $2N$ 的两个序列，分别为序列 $\mathrm{A}: A_1, A_2, \cdots , A_{2N}$，和序列 $\mathrm{B}: B_1, B_2, \cdots , B_{2N}$。

构造一个长度为 $2N$ 的序列 $\mathrm{C}$。满足以下条件：

1. 序列 $\mathrm{C}$ 的第 $i$ 个数 $C_i$，只能从 $A_i$ 和 $B_i$ 中选取。
2. 设 $a$ 为序列 $\mathrm{A}$ 中元素被选取的次数，$b$ 为序列 $\mathrm{B}$ 中元素被选取的次数，则 $a = b = N$。
3. 该序列是一个单调不下降的序列（即 $C_i \le C_{i+1}$），不要求严格单调上升。

如有多解，任意输出一组解即可。

---

输入格式

第一行包含一个数字 $N$，表示序列长度的一半。

第二行包含 $2N$ 个数字，第 $i$ 个数字表示序列 $\mathrm{A}$ 中的第 $i$ 个数字 $A_i$。

第三行包含 $2N$ 个数字，第 $i$ 个数字表示序列 $\mathrm{B}$ 中的第 $i$ 个数字 $B_i$。

---

输出格式

你不需要直接输出这个序列。

你只需要输出一行长度为 $2N$ 的字符串 $s$，如果序列 $\mathrm{C}$ 的第 $i$ 个数从 $A_i$ 中选取，则 $s_i = \text{A}$，否则 $s_i = \text{B}$。

如果无解，输出一行一个数 $-1$。

---

样例 1

输入：

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

输出：

AABABB

解释：序列 $\mathrm{C}$ 为 $(2,5,6,9,12,14)$，分别选取的是 $A_1, A_2, B_3, A_4, B_5, B_6$，可以验证序列 $\mathrm{C}$ 满足所有条件。

---

样例 2

输入：

2
1 4 10 20
3 5 8 13

输出：

BBAA

多解输出任意解。

---

样例 3

输入：

2
3 4 5 6
10 9 8 7

输出：

-1

无法构造满足条件的排列，输出 $-1$。

---

样例 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

输出：

BABBABAABABA

---

数据范围与提示

对于 $100\%$ 的数据，保证

• $1 \le N \le 5 \times 10^5$
• $1 \le A_i \le 10^9 \quad (1 \le i \le 2N)$
• $1 \le B_i \le 10^9 \quad (1 \le i \le 2N)$

子任务 1（$11$ 分）：$1 \le N \le 2000$。

子任务 2（$89$ 分）：没有特殊性质。