Optimal Programs

Writing fast programs is often far from easy, and sometimes speed really matters. Large systems such as operating systems and databases have "bottlenecks" — short code segments that are executed over and over and account for a large part of the total running time. Rewriting such a segment in assembly usually pays off, so here we consider automatically generating optimal assembly code. Given a function described by input/output pairs, produce the shortest program that computes it.

The programs run on a stack machine that supports exactly five commands: ADD, SUB, MUL, DIV, and DUP.

Let $a$ be the element just below the top of the stack and $b$ be the top element. The four arithmetic commands pop both of them and push a single result:

• ADD pushes $a + b$
• SUB pushes $a - b$
• MUL pushes $a \times b$
• DIV pushes the integer quotient $a / b$, truncated toward zero (for example $-7 / 2 = -3$)

DUP pushes an extra copy of the current top element.

At the start of execution the stack holds exactly one integer: the input. At the end the stack must again hold exactly one integer, which is the result of the computation.

The machine enters an error state in any of these cases:

• a DIV is executed while the top element is $0$;
• an ADD, SUB, MUL, or DIV is executed while the stack holds fewer than two elements;
• an operation produces a value whose absolute value exceeds $30000$.

The input is a series of function descriptions. Each description begins with a line containing a single integer $n$ ($n \le 10$), the number of input/output pairs. The next two lines each contain $n$ integers: $x_1, x_2, \ldots, x_n$ on the first line (all distinct) and $y_1, y_2, \ldots, y_n$ on the second line. Every number has absolute value at most $30000$.

The input ends with a description whose first line is $n = 0$; this description is not processed.

For each description, find the shortest program that computes a function $f$ with $f(x_i) = y_i$ for every $i \in {1, \ldots, n}$. The program must not enter an error state when run on any of the inputs $x_i$ (it may enter an error state on other inputs). Consider only programs with at most $10$ commands.

For each description, first output the line Program k, where $k$ is the 1-based description number. Then output the shortest program as its commands separated by single spaces. If several shortest programs exist, output the lexicographically smallest one, comparing the command tokens in the order ADD < DIV < DUP < MUL < SUB. If no program of at most $10$ commands computes the function, output Impossible. If the shortest program has zero commands, output Empty sequence. Print a blank line between consecutive descriptions.