비밀 프로젝트

사성 전자는 매우 빠른 특수 목적용 맞춤형 프로세서를 만든다. 프로세서는 a-C-M(예를 들면, 1-C-2, 5-C-3)와 같은 이름이 붙어있고, 아래 2가지 연산만 사용할 수 있다.

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

프로세서는 정수와 A와 M으로만 되어있는 프로그램을 입력으로 받은 뒤, 프로그램에 따라 입력받은 정수를 변경하고, 결과를 출력한다. 예를 들어, 1-C-2 프로세서에 2를 입력으로 넣고, AAAM 프로그램을 실행시킨다면, 출력은 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 사이의 숫자이다. (p, q 포함)
2. 출력은 항상 r과 s사이이어야 한다. (r, s 포함)

a-C-M 프로세서와 p, q, r, s가 주어졌을 때, p≤x≤q를 만족하는 모든 x에 대해서, r≤y≤s를 만족하는 y를 출력하는 가장 길이가 짧은 프로그램을 작성하시오. 이때, 조건을 지키는 프로그램이 여러개일 경우, 사전순으로 앞서는 것을 출력한다. (프로그램을 A와 M으로 이루어진 문자열로 생각하고 사전순 비교하면 된다)

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 6개의 정수 a, m, p, q, r, s로 이루어져 있다. (1 ≤ a,m,p,q,r,s ≤ 109, p ≤ q, r ≤ s)

마지막 테스트 케이스의 다음 줄에는 0 여섯개가 주어진다.

각 테스트 케이스에 대해서, 케이스 번호를 출력하고, 문제 설명에 해당하는 프로그램을 출력한다. 만약, 연산을 수행하지 않아도 될 때는 "empty"를 출력하고, 그러한 프로그램을 만드는 것이 불가능할 때에는 "impossible"을 출력한다.

프로그램을 공백으로 구분된 문자열을 출력하면 되고, "nA" 형식과 "nM"형식을 서로 번갈아가면서 출력하면 된다. (n > 0) n은 연속된 A 연산의 개수, 또는 M 연산의 개수이다.

예제 출력의 형식을 참고한다.