Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dp

games

*1600

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Permutation Game

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAfter a long day, Alice and Bob decided to play a little game. The game board consists of $$$n$$$ cells in a straight line, numbered from $$$1$$$ to $$$n$$$, where each cell contains a number $$$a_i$$$ between $$$1$$$ and $$$n$$$. Furthermore, no two cells contain the same number.

A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $$$i$$$ to cell $$$j$$$ only if the following two conditions are satisfied:

- the number in the new cell $$$j$$$ must be strictly larger than the number in the old cell $$$i$$$ (i.e. $$$a_j > a_i$$$), and
- the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $$$|i-j|\bmod a_i = 0$$$).

Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of numbers.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Furthermore, there are no pair of indices $$$i \neq j$$$ such that $$$a_i = a_j$$$.

Output

Print $$$s$$$ — a string of $$$n$$$ characters, where the $$$i$$$-th character represents the outcome of the game if the token is initially placed in the cell $$$i$$$. If Alice wins, then $$$s_i$$$ has to be equal to "A"; otherwise, $$$s_i$$$ has to be equal to "B".

Examples

Input

8

3 6 5 4 2 7 1 8

Output

BAAAABAB

Input

15

3 11 2 5 10 9 7 13 15 8 4 12 6 1 14

Output

ABAAAABBBAABAAB

Note

In the first sample, if Bob puts the token on the number (not position):

- $$$1$$$: Alice can move to any number. She can win by picking $$$7$$$, from which Bob has no move.
- $$$2$$$: Alice can move to $$$3$$$ and $$$5$$$. Upon moving to $$$5$$$, Bob can win by moving to $$$8$$$. If she chooses $$$3$$$ instead, she wins, as Bob has only a move to $$$4$$$, from which Alice can move to $$$8$$$.
- $$$3$$$: Alice can only move to $$$4$$$, after which Bob wins by moving to $$$8$$$.
- $$$4$$$, $$$5$$$, or $$$6$$$: Alice wins by moving to $$$8$$$.
- $$$7$$$, $$$8$$$: Alice has no move, and hence she loses immediately.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/31/2023 03:33:39 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|