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

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Gomory_Hu_Tree

题目描述

题目译自 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

样例输出 1

AABABB

样例解释 1

序列 \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

样例输出 2

BBAA

样例解释 2

多解输出任意解。

样例输入 3

2
3 4 5 6
10 9 8 7

样例输出 3

-1

样例解释 3

无法构造满足条件的排列,输出 -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

样例输出 4

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 分):没有特殊性质。