Tired of calculating the results of some bizarre problems modulo 998244353 or $10^9 + 7$, Little E has designed a puzzle related to 2:

Given a grid of 2 rows and $2^k$ columns, you need to fill the $2^{k+1}$ cells with the integers $1 \sim 2^{k+1}$ without repetition or omission, such that the size relationships between adjacent cells satisfy the following constraints.

Specifically, given three 01 sequences $a, b, c$ of lengths $2^k - 1, 2^k, 2^k - 1$ respectively, a $2 \times 2^k$ matrix $A$ is a solution to the puzzle if and only if it satisfies the following four constraints simultaneously:

1. $A$ contains each integer from $1, 2, \dots, 2^{k+1}$ exactly once;
2. For all $1 \le i < 2^k$, $a_i = [A_{1,i} < A_{1,i+1}]$;
3. For all $1 \le i \le 2^k$, $b_i = [A_{1,i} < A_{2,i}]$;
4. For all $1 \le i < 2^k$, $c_i = [A_{2,i} < A_{2,i+1}]$.

Where $[P]$ takes the value 1 if the condition $P$ is true, and 0 otherwise.

For you, simply finding any solution or determining that no solution exists is too easy. Since it is a puzzle about 2, Little E asks you to calculate the number of solutions to the puzzle modulo 2.

Little E has prepared $t$ puzzles with the same grid size and has compressed them together using efficient compression methods. You need to find the number of solutions modulo 2 for each of these puzzles.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file puzzle.h by adding the following code at the beginning of your program:

#include "puzzle.h"

You must implement the following function in your submitted source file:

unsigned puzzle(int t, int k, std::vector<unsigned> a,
std::vector<unsigned> b, std::vector<unsigned> c);

• $t$ and $k$ represent the number of puzzles and the size of the grid, respectively.
• For $0 \le i < 2^k - 1$, the $j$-th bit ($0 \le j < t$) of $a_i$ in binary represents the constraint on the size relationship between $A_{1,i+1}$ and $A_{1,i+2}$ in the $(j+1)$-th puzzle.
• For $0 \le i < 2^k$, the $j$-th bit ($0 \le j < t$) of $b_i$ in binary represents the constraint on the size relationship between $A_{1,i+1}$ and $A_{2,i+1}$ in the $(j+1)$-th puzzle.
• For $0 \le i < 2^k - 1$, the $j$-th bit ($0 \le j < t$) of $c_i$ in binary represents the constraint on the size relationship between $A_{2,i+1}$ and $A_{2,i+2}$ in the $(j+1)$-th puzzle.
• The function should return a non-negative integer, where the $j$-th bit ($0 \le j < t$) in binary represents the number of solutions modulo 2 for the $(j+1)$-th puzzle.
• For each test case, this function will be called exactly once by the interactor.

Note: In any case, the interactor's running time will not exceed 0.1 seconds, and the memory used is fixed and will not exceed 64 MiB.

Testing Method

The grader.cpp in the problem directory is a reference implementation of the interactor. The final interactor used for testing may differ from this reference, so your solution should not rely on the specific implementation of the interactor.

You can compile your program using the following command:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -static

For the compiled executable: It reads the following data from standard input: The first line contains two positive integers $t, k$, representing the number of puzzles and the grid size. The $(3i-1)$-th line ($1 \le i \le t$) contains a 01 string of length $2^k-1$ representing $a_1 \dots a_{2^k-1}$. The $(3i)$-th line ($1 \le i \le t$) contains a 01 string of length $2^k$ representing $b_1 \dots b_{2^k}$. The $(3i+1)$-th line ($1 \le i \le t$) contains a 01 string of length $2^k-1$ representing $c_1 \dots c_{2^k-1}$. It outputs the following data to standard output: * Output $t$ lines, where the $i$-th line ($1 \le i \le t$) contains a non-negative integer representing the number of solutions modulo 2 for the $i$-th puzzle.

Examples

Input 1

1 2 1
2 1
3 01
4 1
5 1
6 00
7 1

Output 1

1 1
2 0

Input 2

1 4 2
2 100
3 1111
4 100
5 100
6 0000
7 110
8 110
9 1111
10 011
11 010
12 0000
13 010

Output 2

1 1
2 1
3 0
4 0

Additional File Description

In the additional files: 1. grader.cpp is the provided reference implementation of the interactor. 2. puzzle.h is the header file; you do not need to concern yourself with its contents. 3. template_puzzle.cpp is the provided sample code, which you may refer to when implementing your own solution.

Constraints

For all test data: $1 \le t \le 32$, $1 \le k \le 18$; For all $1 \le i < 2^k$, $a_i \in \{0, 1\}$; For all $1 \le i \le 2^k$, $b_i \in \{0, 1\}$; For all $1 \le i < 2^k$, $c_i \in \{0, 1\}$.

Special Property A: $t \le 4$. Special Property B: For all $1 \le i < 2^k$, $b_i \neq b_{i+1}$.

Scoring

Note: You should not attempt to obtain internal information of the interactor through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating. The final judging interactor is different from the sample interactor. * This problem is subject to standard constraints; for example, compilation errors will result in 0 points, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test cases. You may only access variables you have defined and those provided by the interactor; attempting to access other memory addresses may result in compilation or runtime errors.

In addition to the above conditions: * For each test case, you receive full points if and only if the puzzle function returns the correct answer.