该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AdditionalFile3271.zip

#3271. 「JOISC 2020 Day1」建筑装饰 4

标签: 传统 | 时间限制: 1500 ms | 内存限制: 512 MiB |

题目描述

题目译自 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}$ 。满足以下条件：

• 序列 $\mathrm{C}$ 的第 $i$ 个数 $C_i$ ，只能从 $A_i$ 和 $B_i$ 中选取。
• 设 $a$ 为序列 $\mathrm{A}$ 中元素被选取的次数， $b$ 为序列 $\mathrm{B}$ 中元素被选取的次数，则 $a = b = N$ 。
• 该序列是一个单调上升的序列，不要求严格单调上升。

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

输入格式

第一行包含一个数字 $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 (1 \le i \le 2N)$
• $1 \le B_i \le 10^9 (1 \le i \le 2N)$

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

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