레이팅 미적용Industrial Computer Processor Company는 고객의 요구에 맞춘 매우 빠른 특수 목적 처리 장치를 제공한다. \(a-C-m\) 계열의 프로세서(\(1-C-2\)와 \(5-C-3\) 등)는 서로 다른 두 가지 연산만으로 이루어진 명령어 집합을 가진다. 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\) 이하의 수임이 보장된다. 2. 출력은 \(r\) 이상 \(s\) 이하의 어떤 수여야 한다. \(a-C-m\) 프로세서와 수 \(p\), \(q\), \(r\), \(s\)가 주어질 때, \(p \le x \le q\)인 모든 입력 \(x\)에 대해 \(r \le y \le s\)인 어떤 출력 \(y\)를 내는 가장 짧은 \(a-C-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”을 출력한다. 프로그램은 공백으로 구분된(spa\(ce-se\)parated) 문자열들의 나열로 출력하며, “\(n\)A” 형태의 문자열과 “\(n\)M” 형태의 문자열이 번갈아 나온다. 여기서 \(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
ICPC 2011 World Finals Problem A: To Add or to Multiply
Case 1: 1A 2M
Case 2: 1M 2A 1M
Case 3: impossible
Case 4: empty