После долгого дня Алиса и Боб решили сыграть в игру. Игровая доска состоит из \(n\) ячеек на прямой, пронумерованных от \(1\) до \(n\), где каждая ячейка содержит число \(a_i\) в диапазоне от \(1\) до \(n\). Кроме того, никакие две ячейки не содержат одинаковые числа.
Игровая фигурка находится на одной ячейке. Они ходят по очереди, двигая фигурку. Алиса ходит первая. Игрок, который ходит, может передвинуть фигурку с ячейки \(i\) на ячейку \(j\), только если выполняются условия:
- число в новой ячейке \(j\) строго больше, чем в старой ячейке \(i\) (то есть \(a_j > a_i\)), и
- расстояние, на которое передвигается фигурка в этом ходу, должно делиться на число, расположенное в старой ячейке (то есть \(|i-j|\bmod a_i = 0\)).
Проигрывает тот, кто не может сделать ход. Для каждой начальной позиции нужно определить, кто победит при оптимальной игре обоих. Можно доказать, что игра всегда когда-нибудь закончится, то есть всегда есть оптимальная стратегия для одного игрока.
Выходные данные
Выведите \(s\) — строку из \(n\) символов, где \(i\)-й символ представляет результат игры, которая начинается в ячейке \(i\). Если победит Алиса, то \(s_i\) должен быть равен «A»; в другом случае, \(s_i\) должен быть равен «B».
Примечание
В первом примере, если Боб поместит игровую фигурку на число (не на позицию):
- \(1\): Алиса может переместиться на любую ячейку. Она может выбрать число \(7\), из которого у Боба нет выхода.
- \(2\): Алиса может переместиться на числа \(3\) и \(5\). При переходе в \(5\), Боб может выиграть, если переместится в \(8\). Если она выберет \(3\), то она победит, так как Боб сможет переместиться только в \(4\), из которого Алиса сможет переместиться в \(8\).
- \(3\): Алиса может переместиться только в \(4\), после чего Боб побеждает, перемещаясь в \(8\).
- \(4\), \(5\) или \(6\): Алиса побеждает, перемещаясь в \(8\).
- \(7\), \(8\): Алиса не может никуда переместиться, поэтому проигрывает.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
3 6 5 4 2 7 1 8
|
BAAAABAB
|
|
2
|
15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14
|
ABAAAABBBAABAAB
|