A Language for Constants

Interview

Time limit1sMemory limit128 MB

Summary

For each nonzero integer C, output the shortest sequence of C+1/C-1 to start, then INCR and DBL, that builds C, breaking ties by total runtime with DBL cost T and INCR cost 2T.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Math, Implementation
Solved: No attempts yet

Problem

A computer science professor is developing a new programming language called YACL ("Yet Another Constant Language"). The language is intentionally minimal — it has only four instructions:

C+1 — create the constant $1$ .
C-1 — create the constant $-1$ .
INCR — add $1$ to the constant currently being built.
DBL — multiply the constant currently being built by $2$ .

A program is a sequence of these instructions, one per line, executed from top to bottom. To keep programs small and fast, every program must obey these rules:

Every program must start with either C+1 or C-1.
A given constant $C$ must be produced using the fewest possible instructions.
If several programs produce $C$ with the same (minimum) number of instructions, the fastest one must be chosen. For timing, assume DBL runs in $T$ nanoseconds and INCR runs in $2T$ nanoseconds.

For each constant you are given, output a program that generates it while satisfying all of the rules above.

Input

The input contains several test cases. Each test case is a single line holding one non-zero integer constant to be generated, with $-32768 \le C \le 32767$ . A line containing the single integer $0$ marks the end of the input and is not processed.

Output

For each test case, first print a line Constant n, where n is that constant. Then print the most efficient program that generates it, one instruction per line. Print a blank line between consecutive test cases.

Examples1

Example 1

Input

Expected output

Constant 3
C+1
DBL
INCR

Constant -5
C-1
DBL
DBL
INCR
DBL
INCR

Constant 1
C+1

Constant 7
C+1
DBL
INCR
DBL
INCR