Compiler

A small processor was built for one job: show a single number on a laser display board.

Its memory is three 8-bit registers named A, X, and Y, plus a stack with no depth limit. When the program starts, the registers hold unknown values and the stack is empty. A sum keeps only its lowest 8 bits.

The processor understands six instructions.

• PH <reg>: push the value of the register (A, X, or Y) onto the stack.
• PL <reg>: pop the value on top of the stack into the register. If the stack is empty, the program stops.
• AD: pop two values off the stack, then push the lowest 8 bits of their sum.
• ZE <reg>: set the register to zero.
• ST <reg>: set the register to one.
• DI <reg>: send the value of the register to the laser display board and exit.

At most 40 instructions fit on the disk, and a line after the 40th one is never executed.

Given a number $N$, print a program that displays $N$. Many different programs display the same number, so the output section pins down exactly one of them.

• One line containing the number $N$ to display ($0 \le N \le 255$).

Print the program fixed by the rule below, one instruction per line.

If $N = 0$, print ZE A on the first line and DI A on the second line.

If $N \ge 1$, the program keeps 1 in register A and builds $N$ in register X. For $1 \le v \le 255$ define $f(v)$ by $f(1) = 1$, $f(2) = 2$, $f(3) = 3$, and

$f(v) = \min_{2 \le m \le v} \left( m + (v \bmod m) + f(\lfloor v / m \rfloor) \right) \quad (v \ge 4).$

Collect a list of pairs like this. Start with $v = N$, and while $v \ge 4$, take the smallest $m$ that attains the minimum in $f(v)$, append the pair $(m, v \bmod m)$ to the list, and replace $v$ by $\lfloor v / m \rfloor$. Let $a$ be the value of $v$ once it reaches 3 or less, and let $(m_1, d_1), \dots, (m_k, d_k)$ be the appended pairs listed in reverse, so the pair appended last comes first.

The program consists of, in this order:

1. one line ST A,
2. $a$ lines PH A, then $a - 1$ lines AD, then one line PL X,
3. for $i = 1, 2, \dots, k$ in this order: $m_i$ lines PH X, then $d_i$ lines PH A, then $m_i + d_i - 1$ lines AD, then one line PL X,
4. one line DI X.

Register X starts at $a$ and follows $v \leftarrow m_i v + d_i$ for $i = 1, \dots, k$, so it holds $N$ when DI X runs. This program never exceeds 40 instructions.