在一个遥远的国度，有 $N$ 名国会议员（MP）。他们就关于新公投法的修正案展开了激烈而热情的辩论。从周一到周五，所有议员都愉快地来上班，并整天争论不休。

一位勤奋的新闻记者在每个工作日的争论高潮中拍下了议员们在工作场所的照片。她在照片中捕捉到的是互相争吵和怒目而视的议员对。这五张照片已转交给你进行彻底分析。

事实上，每位议员都属于两个政党之一。我们用字母 $A$ 和 $B$ 来表示它们。你的任务是估计哪位议员属于哪个政党，使得你的估计满足以下条件：每位议员与最多两个属于其自身政党的不同成员发生过争吵。

输入格式

输入的第一行包含一个整数 $N$ ($2 \le N \le 200\,000$)，表示议员的人数。议员用 $1$ 到 $N$ 的数字表示。

接下来的五行描述了从周一到周五拍摄的照片。这五行中的每一行都包含了当天照片中正在争吵（互相怒目而视）的议员对列表。

首先给出的是对数 $P$ ($1 \le P \le N/2$)，随后是 $P$ 对格式为 "$K\ L$" 的议员对，其中 $K$ 和 $L$ 是互相怒目而视的议员编号。在每对议员之前都有一个双空格。

当然，每位议员在每行中最多出现一次。

输出格式

输出的第一行也是唯一一行必须包含一个仅由字符 $A$ 和 $B$ 组成的字符串，其中第 $K$ 个字符表示在满足给定条件的划分中第 $K$ 位议员所属的政党。

如果有多种满足条件的方案，输出任意一种即可。

数据范围

在占总分 30% 的测试数据中，满足 $N \le 15$。

样例

输入样例 1

7
2  1 2  7 3
2  1 3  7 4
2  1 4  7 5
2  1 5  7 6
2  1 6  7 2

输出样例 1

ABBBBBA

输入样例 2

10
3  1 2  7 3  9 4
3  1 3  7 4  9 5
3  1 4  7 5  9 6
3  1 5  7 6  9 8
3  1 6  7 8  9 10

输出样例 2

ABBBBBAAAA