Bit Shift Registers

문제

Christopher the engineer is working on a new type of computer processor.

The processor has access to $mm$ different $bb$-bit memory cells (where $m=100m\; =\; 100$ and $b=2000b\; =\; 2000$), which are called registers, and are numbered from $00$ to $m-1m\; -\; 1$. We denote the registers by $r[0]r[0]$, $r[1]r[1]$, $\dots \backslash dots$ , $r[m-1]r[m\; -\; 1]$. Each register is an array of $bb$ bits, numbered from $00$ (the rightmost bit) to $b-1b\; -\; 1$ (the leftmost bit). For each $ii$ ($0\le i\le m-10\; \backslash le\; i\; \backslash le\; m\; -\; 1$) and each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), we denote the $jj$-th bit of register $ii$ by $r[i][j]r[i][j]$.

For any sequence of bits $d_{0}d\_0$, $d_{1}d\_1$ , $\dots \backslash dots$ , $d_{l-1}d\_\{l-1\}$ (of arbitrary length $ll$), the integer value of the sequence is equal to $2^0\cdot d_0+2^1\cdot d_1+\cdots +2^{l-1}\cdot d_{l-1}2^0\; \backslash cdot\; d\_0\; +\; 2^1\; \backslash cdot\; d\_1\; +\; \backslash dots\; +\; 2^\{l-1\}\; \backslash cdot\; d\_\{l-1\}$. We say that the integer value stored in a register $ii$ is the integer value of the sequence of its bits, i.e., it is $2^0\cdot r[i][0]+2^1\cdot r[i][1]+\cdots +2^{b-1}\cdot r[i][b-1]2^0\; \backslash cdot\; r[i][0]\; +\; 2^1\; \backslash cdot\; r[i][1]\; +\; \backslash cdots\; +\; 2^\{b-1\}\; \backslash cdot\; r[i][b\; -\; 1]$.

The processor has $99$ types of instructions that can be used to modify the bits in the registers. Each instruction operates on one or more registers and stores the output in one of the registers. In the following, we use $x:=yx\; :=\; y$ to denote an operation of changing the value of $xx$ such that it becomes equal to $yy$. The operations performed by each type of instruction are described below.

• $move(t,y)move(t,\; y)$: Copy the array of bits in register $yy$ to register $tt$. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=r[y][j]r[t][j]\; :=\; r[y][j]$.
• $store(t,v)store(t,\; v)$: Set register $tt$ to be equal to $vv$, where $vv$ is an array of $bb$ bits. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=v[j]r[t][j]\; :=\; v[j]$.
• $and(t,x,y)and(t,\; x,\; y)$: Take the bitwise-AND of registers $xx$ and $yy$, and store the result in register $tt$. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=1r[t][j]\; :=\; 1$ if both $r[x][j]r[x][j]$ and $r[y][j]r[y][j]$ are $11$, and set $r[t][j]:=0r[t][j]\; :=\; 0$ otherwise.
• $or(t,x,y)or(t,\; x,\; y)$: Take the bitwise-OR of registers $xx$ and $yy$, and store the result in register $tt$. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=1r[t][j]\; :=\; 1$ if at least one of $r[x][j]r[x][j]$ and $r[y][j]r[y][j]$ are $11$, and set $r[t][j]:=0r[t][j]\; :=\; 0$ otherwise.
• $xor(t,x,y)xor(t,\; x,\; y)$: Take the bitwise-XOR of registers $xx$ and $yy$, and store the result in register $tt$. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=1r[t][j]\; :=\; 1$ if exactly one of $r[x][j]r[x][j]$ and $r[y][j]r[y][j]$ is $11$, and set $r[t][j]:=0r[t][j]\; :=\; 0$ otherwise.
• $not(t,x)not(t,\; x)$: Take the bitwise-NOT of register $xx$, and store the result in register $tt$. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=1-r[x][j]r[t][j]\; :=\; 1\; -\; r[x][j]$.
• $left(t,x,p)left(t,\; x,\; p)$: Shift all bits in register $xx$ to the left by $pp$, and store the result in register $tt$. The result of shifting the bits in register $xx$ to the left by $pp$ is an array $vv$ consisting of $bb$ bits. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), $v[j]=r[x][j-p]v[j]\; =\; r[x][j\; -\; p]$ if $j\ge pj\; \backslash ge\; p$, and $v[j]=0v[j]\; =\; 0$ otherwise. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=v[j]r[t][j]\; :=\; v[j]$.
• $right(t,x,p)right(t,\; x,\; p)$: Shift all bits in register $xx$ to the right by $pp$, and store the result in register $tt$. The result of shifting the bits in register $xx$ to the right by $pp$ is an array $vv$ consisting of $bb$ bits. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), $v[j]=r[x][j+p]v[j]\; =\; r[x][j\; +\; p]$ if $j\le b-1-pj\; \backslash le\; b\; -\; 1\; -\; p$, and $v[j]=0v[j]\; =\; 0$ otherwise. For each $jj$ ($0\le j\le b-10\; \backslash le\; j\; \backslash le\; b\; -\; 1$), set $r[t][j]:=v[j]r[t][j]\; :=\; v[j]$.
• $add(t,x,y)add(t,\; x,\; y)$: Add the integer values stored in register $xx$ and register $yy$, and store the result in register $tt$. The addition is carried out modulo $2^{b}2^b$. Formally, let $XX$ be the integer value stored in register $xx$, and $YY$ be the integer value stored in register $yy$ before the operation. Let $TT$ be the integer value stored in register $tt$ after the operation. If , set the bits of $tt$, such that $T=X+YT\; =\; X\; +\; Y$. Otherwise, set the bits of $tt$, such that $T=X+Y-2^{b}T\; =\; X\; +\; Y\; -\; 2^b$.

Christopher would like you to solve two types of tasks using the new processor. The type of a task is denoted by an integer $ss$. For both types of tasks, you need to produce a program, that is a sequence of instructions defined above.

The input to the program consists of $nn$ integers $a[0]a[0]$, $a[1]a[1]$, $\dots \backslash dots$ , $a[n-1]a[n\; -\; 1]$, each having $kk$ bits, i.e., ($0\le i\le n-10\; \backslash le\; i\; \backslash le\; n\; -\; 1$). Before the program is executed, all of the input numbers are stored sequentially in register $00$, such that for each $ii$ ($0\le i\le n-10\; \backslash le\; i\; \backslash le\; n\; -\; 1$) the integer value of the sequence of $kk$ bits $r[0][i\cdot k]r[0][i\; \backslash cdot\; k]$, $r[0][i\cdot k+1]r[0][i\; \backslash cdot\; k\; +\; 1]$, $\dots \backslash dots$ , $r[0][(i+1)\cdot k-1]r[0][(i\; +\; 1)\; \backslash cdot\; k\; -\; 1]$ is equal to $a[i]a[i]$. Note that $n\cdot k\le bn\; \backslash cdot\; k\; \backslash le\; b$. All other bits in register $00$ (i.e., those with indices between $n\cdot kn\; \backslash cdot\; k$ and $b-1b\; -\; 1$, inclusive) and all bits in all other registers are initialized to $00$.

Running a program consists in executing its instructions in order. After the last instruction is executed, the output of the program is computed based on the final value of bits in register $00$. Specifically, the output is a sequence of $nn$ integers $c[0]c[0]$, $c[1]c[1]$, $\dots \backslash dots$ , $c[n-1]c[n\; -\; 1]$, where for each $ii$ ($0\le i\le n-10\; \backslash le\; i\; \backslash le\; n\; -\; 1$), $c[i]c[i]$ is the integer value of a sequence consisting of bits $i\cdot ki\; \backslash cdot\; k$ to $(i+1)\cdot k-1(i\; +\; 1)\; \backslash cdot\; k\; -\; 1$ of register $00$. Note that after running the program the remaining bits of register $00$ (with indices at least $n\cdot kn\; \backslash cdot\; k$) and all bits of all other registers can be arbitrary.

• The first task ($s=0s\; =\; 0$) is to find the smallest integer among the input integers $a[0]a[0]$, $a[1]a[1]$, $\dots \backslash dots$ , $a[n-1]a[n\; -\; 1]$. Specifically, $c[0]c[0]$ must be the minimum of $a[0]a[0]$, $a[1]a[1]$, $\dots \backslash dots$ , $a[n-1]a[n\; -\; 1]$. The values of $c[1]c[1]$, $c[2]c[2]$, $\dots \backslash dots$ , $c[n-1]c[n\; -\; 1]$ can be arbitrary.
• The second task ($s=1s\; =\; 1$) is to sort the input integers $a[0]a[0]$, $a[1]a[1]$, $\dots \backslash dots$ , $a[n-1]a[n\; -\; 1]$ in nondecreasing order. Specifically, for each $ii$ ($0\le i\le n-10\; \backslash le\; i\; \backslash le\; n\; -\; 1$), $c[i]c[i]$ should be equal to the $1+i1\; +\; i$-th smallest integer among $a[0]a[0]$, $a[1]a[1]$, $\dots \backslash dots$ , $a[n-1]a[n\; -\; 1]$ (i.e., $c[0]c[0]$ is the smallest integer among the input integers).

Provide Christopher with programs, consisting of at most $qq$ instructions each, that can solve these tasks.