風変わりな問題の答えを $998244353$ や $10^9+7$ で割った余りを計算することに飽きた 小 E は、$2$ に関するパズルを作りました。

$2$ 行 $2^k$ 列のマス目が与えられます。$1\sim2^{k+1}$ の整数を、重複も抜けもなく $2^{k+1}$ 個のマスに入れ、隣接するマスの大小関係が以下の制約を満たすようにしてください。

具体的には、長さがそれぞれ $2^k-1,2^k,2^k-1$ の 01 列 $a,b,c$ が与えられます。$2\times2^k$ 行列 $A$ がこのパズルの解であるとは、次の四つの条件をすべて満たすことをいいます。

1. $A$ は $1,2,\ldots,2^{k+1}$ の各整数をちょうど一度ずつ含む。
2. すべての $1\le i<2^k$ について、$a_i=[A_{1,i}<A_{1,i+1}]$ が成り立つ。
3. すべての $1\le i\le2^k$ について、$b_i=[A_{1,i}<A_{2,i}]$ が成り立つ。
4. すべての $1\le i<2^k$ について、$c_i=[A_{2,i}<A_{2,i+1}]$ が成り立つ。

ここで、$[P]$ は条件 $P$ が成り立つとき $1$、そうでないとき $0$ です。

あなたにとって、解を一つ見つけることや解がないと判定することだけでは簡単すぎます。$2$ に関するパズルなので、 小 E は解の個数を $2$ で割った余りを求めるよう要求します。

小 E は同じ大きさのマス目を使うパズルを $t$ 個用意し、効率的な圧縮方法でまとめました。それぞれのパズルについて、解の個数を $2$ で割った余りを求めてください。

実装の詳細

参加者は main 関数を実装する必要はなく、実装してはいけません。

提出するプログラムにはヘッダーファイル puzzle.h を含めてください。つまり、プログラムの先頭に次のコードを追加してください。

#include "puzzle.h"

提出するソースファイルに、次の関数を実装してください。

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

• $t,k$ はそれぞれパズルの個数とマス目の大きさを表します。
• $0\le i<2^k-1$ について、$a_i$ の二進表現の第 $j$ ビット（$0\le j<t$）は、第 $j+1$ のパズルの $A_{1,i+1}$ と $A_{1,i+2}$ の大小関係の制約を表します。
• $0\le i<2^k$ について、$b_i$ の二進表現の第 $j$ ビット（$0\le j<t$）は、第 $j+1$ のパズルの $A_{1,i+1}$ と $A_{2,i+1}$ の大小関係の制約を表します。
• $0\le i<2^k-1$ について、$c_i$ の二進表現の第 $j$ ビット（$0\le j<t$）は、第 $j+1$ のパズルの $A_{2,i+1}$ と $A_{2,i+2}$ の大小関係の制約を表します。
• この関数は非負整数を返してください。その二進表現の第 $j$ ビット（$0\le j<t$）は、第 $j+1$ のパズルの解の個数を $2$ で割った余りを表します。
• 各テストケースで、この関数はジャッジライブラリからちょうど一度呼び出されます。

注意：どのような場合でも、ジャッジライブラリの実行時間は 0.1 秒を超えません。使用するメモリ量は一定で、64 MiB を超えません。

プログラムのテスト方法

問題のディレクトリにある grader.cpp はジャッジライブラリの参照実装です。最終的なテストで使われる実装はこの参照実装とは異なります。したがって、解法はこのライブラリの実装に依存してはいけません。

問題のディレクトリで次のコマンドを使うと、実行ファイルをコンパイルできます。

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

コンパイルで得られた実行ファイルについて：

• 実行ファイルは標準入力から次の形式のデータを読み込みます。

  • 入力の最初の行は二つの正整数 $t,k$ を含み、それぞれパズルの個数とマス目の大きさを表します。
  • 入力の第 $3i-1$ 行（$1\le i\le t$）は、長さ $2^k-1$ の 01 文字列 $a_1\ldots a_{2^k-1}$ を含みます。
  • 入力の第 $3i$ 行（$1\le i\le t$）は、長さ $2^k$ の 01 文字列 $b_1\ldots b_{2^k}$ を含みます。
  • 入力の第 $3i+1$ 行（$1\le i\le t$）は、長さ $2^k-1$ の 01 文字列 $c_1\ldots c_{2^k-1}$ を含みます。

• 実行ファイルは標準出力に次の形式のデータを出力します。

  • 出力は $t$ 行です。第 $i$ 行（$1\le i\le t$）は、第 $i$ のパズルの解の個数を $2$ で割った余りを表す非負整数を含みます。

入出力例

入力 1

2 1
1
01
1
1
00
1

出力 1

1
0

入力 2

4 2
100
1111
100
100
0000
110
110
1111
011
010
0000
010

出力 2

1
1
0
0

添付ファイルの説明

添付ファイルについて：

1. grader.cpp は、提供されるジャッジライブラリの参照実装です。
2. puzzle.h はヘッダーファイルです。参加者はその具体的な内容を気にする必要はありません。
3. template_puzzle.cpp は提供されるサンプルコードです。これを参考に自分のコードを実装できます。

小課題

すべてのテストデータについて、次が成り立ちます。

• $1\le t\le32$、$1\le k\le18$。
• すべての $1\le i<2^k$ について、$a_i\in\{0,1\}$。
• すべての $1\le i\le2^k$ について、$b_i\in\{0,1\}$。
• すべての $1\le i<2^k$ について、$c_i\in\{0,1\}$。

特別な性質 A：$t\le4$。

特別な性質 B：すべての $1\le i<2^k$ について、$b_i\ne b_{i+1}$。

小課題

注意：

• 標準入力や標準出力のストリームと直接やり取りするなど、不正な方法でジャッジライブラリの内部情報を取得してはいけません。このような行為は不正行為とみなされます。
• 最終的な採点用ライブラリとサンプルのライブラリは実装が異なります。

この問題には、まず通常の問題と同じ制限が適用されます。 たとえば、コンパイルエラーでは問題全体が 0 点となり、実行時エラー、時間制限超過、メモリ制限超過などでは該当するテストケースが 0 点となります。プログラム内でアクセスできるのは、自分で定義した変数とジャッジライブラリが提供する変数だけです。それ以外のアドレス空間にアクセスしようとすると、コンパイルエラーや実行時エラーになることがあります。

上記の条件に加えて：

• 各テストケースでは、puzzle 関数の呼び出しで返される答えが正しいとき、かつそのときに限り満点が与えられます。