Stack Machine Sequence Construction

This problem involves a new kind of stack machine whose memory is an initially empty sequence. The machine supports three operations:

• $$1$$ – Push the integer $$1$$ into the tail of the sequence. This operation can be executed at any time.
• $$dup$$ – Duplicate the number at the end of the sequence and append the copy. This operation can only be executed when the sequence is non-empty.
• $$add$$ – Remove (and delete) the last two numbers from the sequence, add them, and push the result to the tail of the sequence. This operation can only be performed when the sequence contains at least two numbers.

Given a positive integer $$n$$, your task is to output a program (a sequence of operations) of length no more than 200 such that when the program finishes executing the operations, the sequence contains exactly one number, and that number is precisely $$n$$.

For example, to obtain $$8$$, one possible program is illustrated in the figure below.

inputFormat

The input consists of a single positive integer $$n$$. You can assume that the input is such that a valid sequence of operations of no more than 200 operations exists.

outputFormat

Output a sequence of operations, each on its own line. These operations, when executed in order on the stack machine, should result in a sequence containing a single number equal to $$n$$.

The allowed operations are exactly: 1, dup, and add.

sample

1

1