Vault Breaker

Util received an invitation from Sejun, a MatKor executive, and was allowed into the MatKor executive room. Sejun's Codeforces handle is SafeSpot, so the executive room has a vault.

The vault's password is an $N$-digit number in base $B$, and it can start with $0$. The monitor shows the $N$-digit base-$B$ number $S=\overline{S_{N-1}S_{N-2}\cdots S_1S_0}_{(B)}$. The number on the monitor can be changed with two kinds of buttons. Only one button can be pressed at a time. Each button does the following when pressed.

• Button A. Adds $1$ to the displayed number. If the result has more than $N$ digits, only the last $N$ digits are shown. In other words, $S\leftarrow (S+1)\bmod B^N$.
• Button B. Adds $1$ to each digit of the displayed number. If a digit becomes $B$, it becomes $0$. In other words, for every $i$, $S_i\leftarrow (S_i+1)\bmod B$.

While Sejun is away, the curious Util decides to press the buttons on the vault. Pressing only one button over and over is boring, so Util will press both A and B at least once. However, if the value is different from its starting state, Sejun may notice that Util tampered with the vault. So Util wants the number on the monitor to be $S$ again when the operations finish. Since Util does not know when Sejun will return, Util wants to minimize the number of button presses.

Help Util press the vault buttons as few times as possible so that the number becomes $S$ again. Both buttons must be pressed at least once.

The $N$-digit base-$B$ number $S=\overline{S_{N-1}S_{N-2}\cdots S_1S_0}_{(B)}$ has the following value.

$S=\overline{S_{N-1}S_{N-2}\cdots S_1S_0}_{(B)}=\sum_{i=0}^{N-1}{S_iB^i}$

The first line contains two integers, $N$ ($1 \le N \le 100\,000$), the number of digits, and $B$ ($2 \le B \le 100\,000$), the base, separated by a space.

The second line contains $N$ integers $S_{N-1}, S_{N-2}, \cdots, S_1, S_0$ ($0 \le S_i < B$), which give each digit of $S$, separated by spaces.

On the first line, print the minimum number of button presses $V$. If $V$ is greater than $4\,000\,000$, print -1 instead.

If $V$ is at most $4\,000\,000$, print a string of length $V$ on the second line. Each character is A or B, and the string gives the order in which the buttons are pressed.

If several sequences have the minimum length, print any one of them.

Sejun's Codeforces handle is SafeSpot.