Bob 和 Alice 正在玩一个游戏。首先，他们商定一个数字 $x$，并选择一个长度为 $N$ 的序列，记为 $a_1, a_2, \dots, a_N$。

游戏过程如下：Bob 和 Alice 轮流进行操作，Bob 先手。在玩家的回合中，他们必须执行以下操作：

• 选择一个下标集合 $S \subseteq \{1, \dots, N\}$。
• 对于每个 $i \in S$，选择 $x$ 的一个约数 $d_i$，并将 $a_i$ 修改为 $a_i / \gcd(a_i, d_i)$。
• 注意，对于不同的 $i$ 所选择的约数 $d_i$ 不需要相同。
• 只要序列中至少有一个数字的值减小，该操作即为有效。

当然，无法执行有效操作的玩家输掉游戏。

给定该序列，你需要对于 $x = 1, 2, \dots, K$，判断在双方均采取最优策略的情况下，是 Bob 获胜还是 Alice 获胜。

输入格式

第一行包含两个整数 $N$ 和 $K$：序列的长度和需要回答的查询数量（$1 \le N \le 3 \cdot 10^5$；$1 \le K \le 10^6$）。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，即序列的内容（$1 \le a_i \le 10^6$）。

输出格式

输出一个长度为 $K$ 的字符串，记为 $s_1s_2 \dots s_K$，其中字符 $s_i$ 表示当初始数字为 $x = i$ 时谁会获胜。字符 “B” 表示 Bob 获胜，“A” 表示 Alice 获胜。

样例

样例输入 1

4 6
4 5 4 9

样例输出 1

AAABBA

样例输入 2

6 10
3 1 4 1 5 9

样例输出 2

AABBBBABBB