题目描述

工业计算机处理器公司为顾客量身定做了非常快速、用于专门目的的处理单元。a-C-m 系列的处理器（比如 1-C-2 和 5-C-3）的指令集只有两种操作：

• A：数值加 $a$；
• M：数值乘 $m$。

处理器接收一个整数，执行一个 $A$ 和 $M$ 的指令序列（即程序）来修改输入，然后输出结果。

举个例子，1-C-2 处理器执行程序 AAAM 处理输入 $2$ 返回输出 $10$（计算过程是 $2\to3\to4\to5\to10$），然而5-C-3 处理器用相同的程序和输入返回 $51$（$2\to7\to12\to17\to51$）。

你是一个被指定做一个顶级秘密项目的 a-C-m 程序员。这意味着你不会被告知你的程序执行的精确输入。但会得到四个特别的值 $p,q,r,s$，以及下列条件：

1. 输入保证是一个在 $p,q$ 之间的数
2. 输出必须是一个在 $r,s$ 之间的数。

给你一个 a-C-m 处理器和 $p,q,r,s$ 这四个数。

你的工作是构想最短的 a-C-m 程序，使得满足 $p\leq x\leq q$ 的任意 $x$ 返回一个输出 $y$ 使得 $r\leq y\leq s$。如果有多个最短的程序，选择字典序最小的，而一个程序即是由 A 和 M 组成的字符串。

输入格式

输入包含多组数据。

每组数据在一行中给你 $6$ 个整数 $a,m,p,q,r,s$，每个就像上面描述的一样。

末行输入 $6$ 个 $0$ 作为结束。

输出格式

对于每组数据，在你的程序前输出数据的编号，程序即像上面描述的一样。

如果最好的程序没有操作，输出单词 empty。

如果没有程序满足具体要求，输出单词 impossible。

否则输出一个用空格分隔的字符串序列，任两个相邻的字符串形式分别为 nA 和 nM，$n>0$。前者表示 $n$ 个连续的操作 A，后者表示 $n$ 个连续的操作 M。

1 2 2 3 10 20
1 3 2 3 22 33
3 2 2 3 4 5
5 3 2 3 2 3
0 0 0 0 0 0

Case 1: 1A 2M
Case 2: 1M 2A 1M
Case 3: impossible
Case 4: empty

数据规模与约定

对于 $100\%$ 的数据，$1\leq a,m,p,q,r,s\leq 10^9$。