JOI 王国即将举办奥林匹克运动会。为了迎接来自世界各地的参赛者，从机场通往住宿地的道路上的建筑物将被装饰。从机场开始，共有 $2N$ 座建筑物，编号为 $1$ 到 $2N$。

K 总统负责装饰工程。他向公众征集了装饰方案。在审阅了这些方案后，他最终选择了两个方案，即方案 A 和方案 B。在方案 A 中，建筑物 $i$ ($1 \le i \le 2N$) 的豪华程度为 $A_i$。在方案 B 中，建筑物 $i$ ($1 \le i \le 2N$) 的豪华程度为 $B_i$。

这两个方案都非常好，很难从中做出选择。他决定按以下方式装饰建筑物：对于每座建筑物，选择方案 A 或方案 B 中的一种。为了公平地装饰建筑物，方案 A 将用于 $N$ 座建筑物，方案 B 将用于其余的 $N$ 座建筑物。此外，由于如果从机场到住宿地的豪华程度呈上升趋势，参赛者会感到兴奋，因此必须满足以下条件：对于每个 $1 \le i \le 2N - 1$，满足 $C_i \le C_{i+1}$，其中 $C_i$ 是建筑物 $i$ ($1 \le i \le 2N$) 的豪华程度。

编写一个程序，给定建筑物数量以及每个方案中建筑物的豪华程度，判断是否可能选择满足上述条件的装饰方案，如果可能，输出其中一种装饰方式。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N$ $A_1 \dots A_{2N}$ $B_1 \dots B_{2N}$

输出格式

如果无法选择满足条件的装饰方案，向标准输出输出 -1。 否则，向标准输出输出一个长度为 $2N$ 的字符串 $S$，描述装饰建筑物的方式。其中 $S$ 的第 $i$ 个字符 ($1 \le i \le 2N$) 为 A 表示建筑物 $i$ 选择方案 A，为 B 表示建筑物 $i$ 选择方案 B。如果存在多种满足条件的方案，输出其中任意一种即可。

数据范围

• $1 \le N \le 500\,000$
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le 2N$)
• $1 \le B_i \le 1\,000\,000\,000$ ($1 \le i \le 2N$)

子任务

1. (11 分) $N \le 2\,000$
2. (89 分) 无附加限制

样例

输入 1

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

输出 1

AABABB

说明 1

对于每座建筑物分别选择方案 A, A, B, A, B, B。此时方案 A 和方案 B 各被选择了三次。每座建筑物的豪华程度分别为 2, 5, 6, 9, 12, 14。条件得到满足。

输入 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