비밀 프로젝트

사성 전자는 매우 빠른 특수 목적 맞춤형 프로세서를 만든다. 프로세서에는 $a$-C-$m$(예를 들어 1-C-2, 5-C-3)과 같은 이름이 붙어 있으며, 다음 두 가지 연산만 사용할 수 있다.

• A: $a$를 더한다.
• M: $m$을 곱한다.

프로세서는 정수 하나와 A, M으로만 이루어진 프로그램을 입력으로 받아, 프로그램에 따라 그 정수를 바꾼 뒤 결과를 출력한다. 예를 들어 1-C-2 프로세서에 $2$를 넣고 프로그램 AAAM을 실행하면 $10$을 출력한다($2 \to 3 \to 4 \to 5 \to 10$). 같은 입력을 5-C-3 프로세서에 넣으면 $51$을 출력한다($2 \to 7 \to 12 \to 17 \to 51$).

재헌이는 회사에서 비밀 프로젝트를 맡은 $a$-C-$m$ 프로그래머이다. 비밀 프로젝트이기 때문에 재헌이 자신도 정확히 어떤 프로그램을 만들어야 하는지 모른다. 다만 사장은 $p$, $q$, $r$, $s$가 주어졌을 때 다음 조건을 만족하는 프로그램을 만들라고 했다.

1. 입력은 $p$ 이상 $q$ 이하의 수이다.
2. 출력은 항상 $r$ 이상 $s$ 이하여야 한다.

$a$-C-$m$ 프로세서와 $p$, $q$, $r$, $s$가 주어졌을 때, $p \le x \le q$를 만족하는 모든 $x$에 대해 출력 $y$가 $r \le y \le s$를 만족하도록 하는 가장 짧은 프로그램을 작성하라. 가장 짧은 길이의 프로그램이 여러 개라면 사전순으로 가장 앞서는 것을 출력한다(프로그램을 A와 M으로 이루어진 문자열로 보고 사전순으로 비교하며, A가 M보다 앞선다).

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 여섯 정수 $a$, $m$, $p$, $q$, $r$, $s$로 이루어지며, $1 \le a, m, p, q, r, s \le 10^9$, $p \le q$, $r \le s$이다. 마지막 테스트 케이스 다음 줄에는 $0$ 여섯 개가 주어진다.

각 테스트 케이스마다 케이스 번호와 위에서 설명한 프로그램을 출력한다. 연산이 필요하지 않으면 empty를, 그러한 프로그램을 만드는 것이 불가능하면 impossible을 출력한다.

프로그램은 공백으로 구분된 토큰으로 출력하며, nA 형식과 nM 형식을 번갈아 출력한다($n > 0$). 여기서 $n$은 연속된 A 연산의 개수 또는 M 연산의 개수이다.