UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3957. [WF2011]To Add or to Multiply

Statistics 下载数据

Description

工业计算机处理器公司为顾客量身定做了非常快速、用于专门目的的处理单元。a-C-m系列的处理器(比如1-C-2和5-C-3)的指令集只有两种操作:
  • A 数值加a
  • M 数值乘m
  处理器接收一个整数,执行一个A和M的指令序列(即程序)来修改输入,然后输出结果。举个例子,1-C-2处理器执行程序AAAM处理输入2返回输出10(计算过程是2→3→4→5→10),然而5-C-3处理器用相同的程序和输入返回51(2→7→12→17→51)。
  你是一个被指定做一个顶级秘密项目的a-C-m程序员。这意味着你不会被告知你的程序执行的精确输入。但会得到四个特别的值p,q,r,s,以及下列条件
  1、输入保证是一个在p、q之间的数
  2、输出必须是一个在r,s之间的数。
  给你一个a-C-m处理器和p,q,r,s这四个数。你的工作是构想最短的a-C-m程序,使得任意任意x保证p≤x≤q,返回一个输出y使得r≤y≤s。如果有多个最短的程序,选择字典序最小的,而一个程序即是由A和M组成的字符串。

Input

输入包含多组数据。每组数据在一行中给你6个整数a,m,p,q,r,s,每个就像上面描述的一样。
末行输入6个0作为结束。

Output

对于每组数据,在你的程序前输出数据的编号,程序即像上面描述的一样。输出单词“empty”,如果最好的程序没有操作。输出单词“impossible”如果没有程序满足具体要求。
输出一个用空格分隔的字符串序列,任两个相邻的字符串形式分别为“nA”和“nM”,n>0。前者表示n个连续的操作A,后者表示n个连续的操作M。

Sample Input

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

Sample Output

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

Hint

所有的的a,m,p,q,r,s∈[1,1000000000],且p≤q,r≤s。

Source