C. The Empress
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Note: This is the inverse version of problem "The Emperor" with differences in constraints.

Capoo invented an interesting language named Push-Pop. This language is an interpreted language. The interpreter starts with an empty stack with infinite capacity and reads the first instruction of the custom program. There are only two kinds of instructions in this language:

  • POP a GOTO x; PUSH b GOTO y

    If the top element of the stack is $$$a$$$, then pop the stack once and transfer the control flow to the $$$x$$$-th instruction (which means the next instruction will be the $$$x$$$-th). Otherwise, push an element $$$b$$$ into the stack and transfer the control flow to the $$$y$$$-th instruction.

  • HALT; PUSH b GOTO y

    If the stack is empty, halt the whole program after executing this instruction. Otherwise, push an element $$$b$$$ into the stack and transfer the control flow to the $$$y$$$-th instruction.

Capoo wants to construct a Push-Pop program that halts after executing exactly $$$k$$$ instructions. Due to the naive implementation of the interpreter, a program can contain at most $$$64$$$ instructions.

Input

The only line contains a single integer $$$k$$$ ($$$1\le k \le 2^{31} - 1$$$, $$$k$$$ is odd).

Output

The first line contains an integer $$$n ~(1\le n\le 64)$$$ denoting the number of instructions, and then follows $$$n$$$ lines denoting the Push-Pop program. For each instruction, $$$1\le a,b\le 128,~ 1\le x,y\le n$$$ should hold.

It is guaranteed that a solution exists for given input.

Examples
Input
1
Output
1
HALT; PUSH 1 GOTO 1
Input
5
Output
5
POP 1 GOTO 2; PUSH 1 GOTO 2
HALT; PUSH 1 GOTO 3
POP 1 GOTO 4; PUSH 2 GOTO 4
POP 1 GOTO 2; PUSH 2 GOTO 4
HALT; PUSH 99 GOTO 4
Note

For the second example, instructions are: 1(PUSH), 2(PUSH), 3(POP), 4(POP), 2(HALT).

Key differences in constraints comparing to "The Emperor":

  • $$$n \leq 64$$$;
  • The solution will always exists for given input;
  • Program should halt in exactly $$$k$$$ instructions, not to be considered modulo $$$998\,244\,353$$$.