Secret Project

Saseong Electronics builds very fast, special-purpose custom processors. A processor is named like $a$-C-$m$ (for example, 1-C-2 or 5-C-3) and supports only the following two operations:

• A: add $a$.
• M: multiply by $m$.

The processor takes an integer together with a program consisting only of the letters A and M. It transforms the integer according to the program and outputs the result. For example, feeding $2$ into a 1-C-2 processor and running the program AAAM outputs $10$ ($2 \to 3 \to 4 \to 5 \to 10$). Feeding the same input into a 5-C-3 processor outputs $51$ ($2 \to 7 \to 12 \to 17 \to 51$).

Jaeheon is an $a$-C-$m$ programmer assigned to a secret project. Because it is secret, even Jaeheon does not know exactly what program he must write. However, his boss told him that, given $p$, $q$, $r$, and $s$, he must write a program satisfying:

1. The input is a number between $p$ and $q$ (inclusive).
2. The output must always be between $r$ and $s$ (inclusive).

Given the $a$-C-$m$ processor and $p$, $q$, $r$, $s$, write the shortest program such that for every $x$ with $p \le x \le q$, the output $y$ satisfies $r \le y \le s$. If several programs of the shortest length work, output the lexicographically smallest one (treat a program as a string of A and M and compare lexicographically, where A precedes M).

The input consists of several test cases. Each test case contains six integers $a$, $m$, $p$, $q$, $r$, $s$ with $1 \le a, m, p, q, r, s \le 10^9$, $p \le q$, and $r \le s$. The line after the last test case contains six zeros.

For each test case, print the case number followed by the program described above. If no operation is needed, print empty; if it is impossible to build such a program, print impossible.

Print the program as space-separated tokens, alternating between the forms nA and nM (with $n > 0$), where $n$ is the number of consecutive A operations or M operations.