#P6891. [JOISC2020] ビルの飾り付け 4

[JOISC2020] ビルの飾り付け 4

题目背景

JOISC2020 Day 1 T1

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

题目描述

给定两个长度为 2n2n 的序列 A,BA,B,构造一个长度为 2n2n 的序列 CC 满足以下条件:

  • 对于 1i2n1\leq i\leq 2nCiC_i 只能从 AiA_iBiB_i 中选取

  • CiC_iAiA_i 中选取的次数和从 BiB_i 中选取的次数都恰好为 nn

  • CC 为单调不降的序列。

如果满足条件的 CC 有多个,只需要输出一个。

输入格式

第一行一个正整数 nn

第二行 2n2n 个数字,第 ii 个为 AiA_i

第三行 2n2n 个数字,第 ii 个为 BiB_i

输出格式

如果无解则输出 1-1,否则按照以下方式输出一个字符串 ss

对于 1i2n1\leq i\leq 2n,如果 CiC_i 是从 AiA_i 选取的则 si=As_i=\texttt{A},否则 si=Bs_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]C=[2,5,6,9,12,14],可以自行这是满足条件的方案。

样例 2 解释

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

样例 3 解释

没有满足条件的方案。

子任务

子任务 特殊性质 分数
11 1n2×1031\leq n\leq 2\times 10^3 1111
22 8989

对于 100%100\% 的数据,1n5×105,1Ai,Bi1091\leq n\leq 5\times 10^5,1\leq A_i,B_i\leq 10^9