SP9440 ADDMUL - To Add or to Multiply

The Industrial Computer Processor Company offers very fast, special purpose processing units tailored to customer needs. Processors of the a-C-m family (such as the 1-C-2 and the 5-C-3) have an instruction set with only two different operations: _A add a_ _M multiply by m_ The processor receives an integer, executes a sequence of A and M operations (the program) that modifies the input, and outputs the result. For example, the 1-C-2 processor executing the program AAAM with the input 2 yields the output 10 (the computation is 2 → 3 → 4 → 5 → 10), while the 5-C-3 processor yields 51 with the same program and input (2→ 7 → 12 → 17 → 51). You are an a-**C**-m programmer assigned to a top secret project. This means that you have not been told the precise computation your program should perform. But you are given particular values _p_, _q_, _r_, and _s_ and the following conditions: 1\. The input is guaranteed to be a number between _p_ and _q_. 2\. The output must be some number between _r_ and _s_. Given an a-**C**-m processor and the numbers _p_, _q_, _r_, and _s_, your job is to construct the shortest a-**C**-m program which, for every input _x_ such that _p_ x q, yields some output _y_ such that _r_ y s. If there is more than one program of minimum length, choose the one that come first lexicographically, treating each program as a string of As and Ms.

The input contains several test cases. Each test case is given by a line with the six integers _a_, _m_, _p_, _q_, _r_, and _s_ as described above (1 a, m, p, q, r, s p q and _r_ s). The last test case is followed by a line with six zeros.

For each test case, display its case number followed by the best program as described above. Display the word “empty” if the best program uses no operations. Display the word “impossible” if there is no program meeting the specifications. Display the program as a sequence of space-separated strings, alternating between strings of the form “nA” and strings of the form “nM”, where _n_ > 0. Strings of the former type indicate _n_ consecutive A operations, and strings of the latter type indicate _n_ consecutive M operations. Follow the format of the sample output.