После долгого дня Алиса и Боб решили сыграть в игру. Игровая доска состоит из \(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».