쿼터너리 컴퓨터

경근이는 새로운 컴퓨터를 발명했다. 이 컴퓨터는 다른 컴퓨터와 달리 이진법이 아니라 사진법으로 자료를 저장한다.

이 컴퓨터에서 $p + q$와 $p \oplus q$의 연산 결과는 아래 표와 같다. 표에서 행은 $p$, 열은 $q$이다.

$p + q$

$p \oplus q$

경근이는 자신이 발명한 컴퓨터가 너무나 혁신적이라고 생각해서, 한시라도 빨리 써 보고 싶은 마음에 컴퓨터를 직접 만들었다.

예산을 아주 적게 들여 임시로 만든 것이라서 이 컴퓨터는 변수를 $N$개만 저장하고, 각 변수에는 0 이상 3 이하의 정수 하나만 들어간다. 경근이는 편의상 각 변수에 0 이상 $N - 1$ 이하의 번호를 붙였고, $i$번 변수를 $v_i$라고 부르기로 했다.

경근이는 시간과 정성을 들여 꼭 필요하다고 판단한 기본 명령 네 가지를 만들었다.

• addv x y z ($0 \le x, y, z \le N - 1$, $x$, $y$, $z$는 모두 정수): $v_x$에 $v_y + v_z$의 값을 대입한다.
• xorv x y z ($0 \le x, y, z \le N - 1$, $x$, $y$, $z$는 모두 정수): $v_x$에 $v_y \oplus v_z$의 값을 대입한다.
• addc x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$, $x$, $y$, $z$는 모두 정수): $v_x$에 $v_y + z$의 값을 대입한다.
• xorc x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$, $x$, $y$, $z$는 모두 정수): $v_x$에 $v_y \oplus z$의 값을 대입한다.

경근이는 기본 명령 $M$개를 나열한 코드를 작성했다. 코드를 컴파일하면 프로그램이 생성된다. 이 프로그램은 명령을 실행하기 전에 각 변수 $v_i$에 저장할 값을 입력받고, 코드에 있는 $M$개의 명령을 순서대로 하나씩 실행한 다음, 모든 명령을 실행한 뒤 각 변수 $v_i$에 저장되어 있는 값을 출력한다. 편의상 입력을 $a_0, a_1, \dots, a_{N-1}$로, 출력을 $b_0, b_1, \dots, b_{N-1}$로 나타내자.

아쉽게도 경근이의 구현 실수 탓에, 모든 변수 $v_i$에는 처음에 저장할 수 없는 값 $f_i$ ($0 \le f_i \le 3$)가 하나씩 있다. 따라서 $a_i \ne f_i$여야 하므로 $a_i$로 가능한 값은 0, 1, 2, 3 중 $f_i$가 아닌 세 수이다. 그러므로 가능한 입력은 모두 $3^N$가지이다.

경근이는 프로그램을 완벽하게 작성했는지 알고자 가능한 입력을 모두 살펴보기로 한다. 결과를 기록하려고 $N$쪽으로 된 노트를 샀고, 각 쪽에 0 이상 $N - 1$ 이하의 정수 번호를 붙였다. 경근이는 가능한 입력을 모두 만들어 하나씩 프로그램에 넣어 보면서, 각 입력에 대한 프로그램의 출력 $b_0, b_1, \dots, b_{N-1}$을 얻은 뒤 $b_i$의 값을 $i$번 쪽에 적는다.

모든 입력을 다 살펴본 뒤 $i$번 쪽에 적혀 있는 수의 합을 $s_i$라고 하자. 경근이는 작업을 시작하기 전에 최소한의 안전 장치를 마련하고자 모든 $i$에 대해 $s_i$를 4로 나눈 나머지를 알고자 한다.

첫째 줄에 변수의 수 $N$ ($1 \le N \le 18$)과 명령의 수 $M$ ($0 \le M \le 400$)이 주어진다.

둘째 줄에 $f_0, f_1, \dots, f_{N-1}$ ($0 \le f_i \le 3$)이 공백을 사이에 두고 주어진다. 여기서 $f_i$는 명령을 실행하기 전에 변수 $v_i$에 저장할 수 없는 값이며, 정수이다.

이후 $M$개의 줄에 명령이 실행되는 순서대로 한 줄에 하나씩 주어진다. 이 중 $j$ ($1 \le j \le M$)번째 줄의 형식은 다음과 같고, 주어지는 수는 모두 정수이며 공백 하나로 구분된다.

• 0 x y z ($0 \le x, y, z \le N - 1$): $j$번째로 실행되는 명령이 addv x y z임을 나타낸다.
• 1 x y z ($0 \le x, y, z \le N - 1$): $j$번째로 실행되는 명령이 xorv x y z임을 나타낸다.
• 2 x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$): $j$번째로 실행되는 명령이 addc x y z임을 나타낸다.
• 3 x y z ($0 \le x, y \le N - 1$, $0 \le z \le 3$): $j$번째로 실행되는 명령이 xorc x y z임을 나타낸다.

$s_i$를 4로 나눈 나머지를 $t_i$라고 할 때, 첫째 줄에 $t_0, t_1, \dots, t_{N-1}$을 공백을 사이에 두고 출력한다.