최적 프로그램

빠른 프로그램을 작성하는 일은 종종 결코 쉽지 않고, 때로는 속도가 정말 중요합니다. 운영체제나 데이터베이스 같은 대규모 시스템에는 수십억 번씩 실행되며 전체 실행 시간의 많은 부분을 차지하는 짧은 "병목" 코드 구간이 있습니다. 이런 구간을 어셈블리로 다시 작성하면 큰 이득을 볼 수 있으므로, 여기서는 최적의 어셈블리 코드를 자동으로 생성하는 문제를 생각합니다. 함수가 입력/출력 쌍으로 주어질 때, 그 함수를 계산하는 가장 짧은 프로그램을 구하세요.

프로그램은 스택 기계 위에서 실행되며, 명령은 정확히 다섯 가지입니다: ADD, SUB, MUL, DIV, DUP.

스택의 맨 위에서 두 번째 원소를 $a$, 맨 위 원소를 $b$라고 합시다. 네 개의 산술 명령은 이 두 원소를 모두 꺼낸 뒤 결과 하나를 넣습니다.

• ADD는 $a + b$를 넣습니다.
• SUB는 $a - b$를 넣습니다.
• MUL은 $a \times b$를 넣습니다.
• DIV는 정수 몫 $a / b$를 넣으며, 몫은 0 방향으로 버림합니다 (예: $-7 / 2 = -3$).

DUP은 현재 맨 위 원소의 복사본을 하나 더 넣습니다.

실행을 시작할 때 스택에는 정수 하나, 즉 입력만 들어 있습니다. 실행이 끝났을 때에도 스택에는 정수 하나만 남아 있어야 하며, 그 값이 계산 결과입니다.

다음 중 하나라도 발생하면 기계는 오류 상태에 빠집니다.

• 맨 위 원소가 $0$인 상태에서 DIV를 실행한 경우
• 스택에 원소가 두 개 미만일 때 ADD, SUB, MUL, DIV 중 하나를 실행한 경우
• 어떤 연산의 결과가 절댓값으로 $30000$을 넘는 경우

입력은 여러 개의 함수 설명으로 이루어집니다. 각 설명의 첫 줄에는 입력/출력 쌍의 개수 $n$ ($n \le 10$)이 주어집니다. 이어지는 두 줄에는 각각 정수 $n$개가 주어지는데, 첫 줄은 $x_1, x_2, \ldots, x_n$ (모두 서로 다름), 둘째 줄은 $y_1, y_2, \ldots, y_n$입니다. 모든 수의 절댓값은 $30000$ 이하입니다.

첫 줄이 $n = 0$인 설명이 나오면 입력이 끝나며, 이 설명은 처리하지 않습니다.

각 설명에 대해, 모든 $i \in \{1, \ldots, n\}$에 대하여 $f(x_i) = y_i$를 만족하는 함수 $f$를 계산하는 가장 짧은 프로그램을 찾으세요. 이 프로그램은 입력 $x_i$들에 대해 실행할 때 오류 상태에 빠져서는 안 됩니다 (다른 입력에 대해서는 오류가 나도 됩니다). 명령이 최대 $10$개인 프로그램만 고려합니다.

각 설명마다 먼저 Program k 줄을 출력합니다 (여기서 $k$는 1부터 시작하는 설명 번호). 그 다음 가장 짧은 프로그램을 명령들 사이를 공백 하나로 구분하여 출력합니다. 가장 짧은 프로그램이 여러 개이면 사전순으로 가장 앞선 것을 출력하며, 명령 토큰의 대소는 ADD < DIV < DUP < MUL < SUB 순서로 비교합니다. 명령이 $10$개 이하인 프로그램으로 함수를 계산할 수 없으면 Impossible을 출력합니다. 가장 짧은 프로그램의 명령이 $0$개이면 Empty sequence를 출력합니다. 서로 이웃한 설명 사이에는 빈 줄을 하나 출력합니다.