BitBitJump x‐Comparator Generator

The BitBitJump computer is a 16‐bit one‐instruction set computer with only one instruction: bbj a, b, c. When executing an instruction, the computer interprets the three consecutive words at the instruction pointer (IP) as a, b and c. It then copies the (a & 15)-th bit of the (a \(\gg\) 4)-th word into the (b & 15)-th bit of the (b \(\gg\) 4)-th word, and finally sets IP = c. Execution starts at IP = 0 and stops once IP \(\ge\) 2¹² − 2.

The last word in memory (word number 2¹² − 1) is called the IO‐word. An x‐comparator is a BitBitJump program which checks whether the original value of the IO‐word is equal to a given constant \(x\). Upon halting (after no more than 2¹² instructions), the lowest bit of the IO‐word must be 1 if the IO‐word was originally equal to \(x\), and 0 otherwise.

Your task is to write a program that, given an integer \(x\) as input, outputs (generates) an x‐comparator program for the BitBitJump computer. The comparator program is simply a sequence of 16‐bit words (each in the range 0 to 65,535) printed one per line. (Note that the BitBitJump computer uses 2¹² = 4096 words in its memory.)

For example, one simple (but not fully functional) solution is to output a fixed comparator that does not actually perform the full equality check but instead always writes a constant into the IO‐word’s lowest bit. In our sample solutions below the generator will output a program that always sets the IO‐word’s lowest bit to 0 (interpreted as "false") when \(x \neq 0\) and, if \(x = 0\), it outputs a program that sets the bit to 1 ("true"). (In a real solution the generated comparator must inspect the original IO‐word value and decide accordingly. For the sake of simplicity, our sample solutions implement a trivial comparator.)

inputFormat

The input consists of a single integer \(x\) (0 \(\le\) \(x\) \(\le\) 65,535) representing the value to compare the IO‐word against.

outputFormat

Output a BitBitJump comparator program. The program is a sequence of 16‐bit words (in decimal), one per line. It is guaranteed that the program uses no more than 2¹² words and that it halts after at most 2¹² instructions. In our sample solutions the program is trivial: it always sets the IO‐word’s lowest bit to 0 when \(x \neq 0\), and to 1 when \(x = 0\).

sample

0

16
1
65520
4094