33028번 - BitBitJump 스페셜 저지다국어

문제

BitBitJump is a one instruction set computer. Thus, it has only one instruction: bbj a, b, c, which copies an $a$-th bit of memory to the $b$-th bit of memory and then jumps to address $c$.

Let's consider a 16-bit BitBitJump computer. It has 2ドル^{16}$ bits of memory organized in 2ドル^{12}$ 16-bit words. Words are counted from 0, and bits in a word are counted from the least significant (0-th) bit to the most significant (15-th) bit.

This computer has a single instruction pointer register $(\mathrm{IP}),ドル and execution starts with $\mathrm{IP}=0$. If the current $\mathrm{IP} \ge 2^{12}-2,ドル the computer stops. Otherwise, it uses the $\mathrm{IP}$-th word as $a,ドル the $(\mathrm{IP}+1)$-th word as $b,ドル the $(\mathrm{IP}+2)$-th word as $c,ドル and performs the bbj a, b, c instruction: copies the $(a \mathbin{\&} 15)$-th bit of the $(a \gg 4)$-th word to the $(b \mathbin{\&} 15)$-th bit of the $(b \gg 4)$-th word, and sets $\mathrm{IP}=c$. Here, '$\mathbin{\&}$' represents bitwise AND, and '$\gg$' represents bitwise shift right operation. Notice that the value of $c$ is read from memory after the bit copy, so if the instruction modified its own $c,ドル the new value will be used for $\mathrm{IP}$.

For example, the bbj 32, 35, 5 instruction placed at the memory start will be executed as follows:

1. $a=32$ and $b=35$ are read from the memory.
2. The 0-th bit of the 2-nd word (its value is 5ドル \mathbin{\&} 1 = 1$) will be copied to the 3-rd bit of the same word, so the 2-nd word will have the value of 5ドル + 2^3 = 13$.
3. Then $c=13$ is read from memory, and $\mathrm{IP}$ is set to 13.

Let's call the $(2^{12}-1)$-th word (2ドル^{16}-16 \ldots 2^{16}-1$-th bits of memory) an IO-word. An $x$-comparator is a program which checks whether the value of the IO-word is equal to $x$. It should stop after execution of no more than 2ドル^{12}$ instructions, leaving the lowest bit of the IO-word equal to 1ドル$ if the original value of the IO-word was equal to $x,ドル and 0ドル$ otherwise.

Write a program that generates an $x$-comparator for the given value of $x$.

입력

The input contains a single decimal integer $x$ (0ドル \le x < 2^{16}$) --- the value for which to build the $x$\nobreakdash-comparator.

출력

The output should contain the $x$-comparator program dump. Dump consists of values for the first $n$ words of the memory (1ドル \le n \le 2^{12}-1$). All other words, except the IO-word, are filled with zeroes.

For each of the $n$ words, output its value as a four-character hexadecimal number. Values should be delimited by space or new line characters.

제한

힌트

A dump in the sample output contains a 0-comparator. It consists of the following blocks:

• 16 instructions: the $i$-th of them, counting from 0, copies the $i$-th bit of the input word to the 6-th bit of its own $c$. If the copied bit is zero, it will proceed to the next instruction; otherwise, the next instruction number will be increased by 64.
• The following instruction copies the 4-th bit of the 0-th word (value 1) to the 0-th bit of the IO-word and jumps to the stop address.
• 16 unused words filled with 0.
• 16 equal instructions (starting from word 67). Each of them copies the 0-th bit of the 0-th word (value 0) to the 0-th bit of the IO-word and jumps to the stop address.