Quaternary Computer

Gyeonggeun invented a new computer. Unlike other computers, it stores data in base 4 instead of base 2.

On this computer the results of $p + q$ and $p \oplus q$ are given by the tables below. The row is $p$ and the column is $q$.

$p + q$

$p \oplus q$

Gyeonggeun thought his invention was so innovative that he wanted to try it out at once, so he built the machine himself.

He put it together temporarily on a very small budget, so it stores only $N$ variables, and each variable holds a single integer from 0 to 3. For convenience Gyeonggeun numbered the variables from 0 to $N - 1$ and calls variable number $i$ by the name $v_i$.

Gyeonggeun took his time and made the four basic commands he judged necessary.

• addv x y z ($0 \le x, y, z \le N - 1$, and $x$, $y$, $z$ are all integers): assigns the value of $v_y + v_z$ to $v_x$.
• xorv x y z ($0 \le x, y, z \le N - 1$, and $x$, $y$, $z$ are all integers): assigns the value of $v_y \oplus v_z$ to $v_x$.
• addc x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$, and $x$, $y$, $z$ are all integers): assigns the value of $v_y + z$ to $v_x$.
• xorc x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$, and $x$, $y$, $z$ are all integers): assigns the value of $v_y \oplus z$ to $v_x$.

Gyeonggeun wrote code that lists $M$ basic commands. Compiling the code produces a program. Before running any command, the program reads the value to store in each variable $v_i$, executes the $M$ commands of the code one at a time in order, and then prints the value held by each variable $v_i$ once all commands are done. For convenience, write the input as $a_0, a_1, \dots, a_{N-1}$ and the output as $b_0, b_1, \dots, b_{N-1}$.

Because of a mistake in Gyeonggeun's implementation, every variable $v_i$ has one value $f_i$ ($0 \le f_i \le 3$) that cannot be stored in it at the start. So $a_i \ne f_i$ must hold, and $a_i$ can be any of the three values among 0, 1, 2, 3 other than $f_i$. There are therefore $3^N$ possible inputs.

To learn whether he wrote the program correctly, Gyeonggeun decides to go through every possible input. He bought a notebook of $N$ pages and numbered the pages from 0 to $N - 1$. He builds every possible input, feeds each one to the program once, takes the output $b_0, b_1, \dots, b_{N-1}$ for that input, and writes the value of $b_i$ on page $i$.

After every input has been gone through, let $s_i$ be the sum of the numbers written on page $i$. Before starting the work, Gyeonggeun wants one minimal safeguard: the remainder of $s_i$ divided by 4, for every $i$.

The first line contains the number of variables $N$ ($1 \le N \le 18$) and the number of commands $M$ ($0 \le M \le 400$).

The second line contains $f_0, f_1, \dots, f_{N-1}$ ($0 \le f_i \le 3$), separated by spaces. Here $f_i$ is the value that cannot be stored in variable $v_i$ before the commands run, and it is an integer.

Each of the next $M$ lines contains one command, in the order the commands run. Line $j$ ($1 \le j \le M$) has one of the formats below. Every number given is an integer, and the numbers are separated by single spaces.

• 0 x y z ($0 \le x, y, z \le N - 1$): the $j$th command to run is addv x y z.
• 1 x y z ($0 \le x, y, z \le N - 1$): the $j$th command to run is xorv x y z.
• 2 x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$): the $j$th command to run is addc x y z.
• 3 x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$): the $j$th command to run is xorc x y z.

Let $t_i$ be the remainder of $s_i$ divided by 4. Print $t_0, t_1, \dots, t_{N-1}$ on the first line, separated by spaces.