经过漫长的一天,爱丽丝和鲍勃决定玩一个小游戏。游戏板由沿直线排列的 $$$n$$$ 个单元格组成,编号从 $$$1$$$ 到 $$$n$$$,其中每个单元格包含一个介于 $$$1$$$ 和 $$$n$$$ 之间的数字 $$$a_i$$$。此外,没有两个单元格包含相同的数字。
一个令牌被放置在其中一个单元格中。他们轮流在棋盘上移动令牌,爱丽丝先移动。仅当满足以下两个条件时,当前玩家才能从单元格$$$i$$$移动到单元格$$$j$$$:
- 新单元格 $$$j$$$ 中的数字必须严格大于旧单元格 $$$i$$$ 中的数字(即 $$$a_j > a_i$$$),并且
- 令牌在本回合中移动的距离必须是旧单元格中数字的倍数(即 $$$|i-j|\bmod a_i = 0$$$)。
谁无法采取行动,谁就输了。对于每个可能的起始位置,如果他们都发挥最佳,则确定谁获胜。可以证明,游戏总是有限的,即其中一个玩家总是有获胜策略。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数字的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。此外,不存在一对索引 $$$i \neq j$$$ 使得 $$$a_i = a_j$$$。
输出
打印 $$$s$$$ — 由 $$$n$$$ 字符组成的字符串,其中第 $$$i$$$ 个字符代表游戏的结果(如果令牌最初放置在单元格 $$$i$$$ 中)。如果 Alice 获胜,则 $$$s_i$$$ 必须等于“A”;否则,$$$s_i$$$ 必须等于“B”。
示例
输入 #1
8 3 6 5 4 2 7 1 8
输出 #1
BAAAABAB
输入 #2
15 3 11 2 5 10 9 7 13 15 8 4 12 6 1 14
输出 #2
ABAAAABBBAABAAB
注意
在第一个示例中,如果 Bob 将令牌放在数字上(而不是位置):
- $$$1$$$:爱丽丝可以移动到任何数字。她可以通过选择 $$$7$$$ 来获胜,而 Bob 对此没有任何动作。
- $$$2$$$:Alice 可以移动到 $$$3$$$ 和 $$$5$$$。移动到 $$$5$$$ 后,Bob 可以通过移动到 $$$8$$$ 获胜。如果她选择 $$$3$$$,她就赢了,因为 Bob 只能移动到 $$$4$$$,而 Alice 可以从 $$$8$$$ 移动到 $$$8$$$。
- $$$3$$$:Alice 只能移动到 $$$4$$$,之后 Bob 通过移动到 $$$8$$$ 获胜。
- $$$4$$$、$$$5$$$ 或 $$$6$$$:Alice 移动到 $$$8$$$ 获胜。
- $$$7$$$、$$$8$$$:爱丽丝没有动作,因此她立即失败。