問題文

非負整数 x, y, z に対し、 以下の条件をすべて満たす非負整数の組 (a,b,c) の個数を f(x, y, z) と定めます。

• a \ \mathrm{AND} \ b \ \mathrm{AND} \ c = x
• a \ \mathrm{OR} \ b \ \mathrm{OR} \ c = y
• a + b + c = z

ここで a \ \mathrm{AND} \ b は a と b のビットごとの論理積を表し、a \ \mathrm{OR} \ b は a と b のビットごとの論理和を表します。

正整数 N, M と、 0, 1, ? からなる長さ N の文字列 X,Y,Z が与えられます。

X の ? を 0 または 1 に置き換えて得られる文字列を 2 進数の整数と解釈したものとしてあり得る整数全体の集合を S_X とおきます。Y に対する S_Y 、 Z に対する S_Z も同様に定義します。

k = 0, 1, \ldots, M-1 について、以下の問題を解いてください。

• x \in S_X, y \in S_Y, z \in S_Z を満たす整数の 3 つ組 (x, y, z) であって、f(x, y, z) \equiv k \pmod{M} を満たすものが存在するか判定せよ。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• 1 \leq T \leq 3000
• 1 \leq N \leq 3000
• 1 \leq M \leq 10^6
• X, Y, Z は 0, 1 , ? からなる長さ N の文字列
• すべてのテストケースにおける N の総和は {3000} 以下
• すべてのテストケースにおける M の総和は 10^6 以下
• N,M は整数

入力例 1

3
3 5
0?1
?01
?11
5 7
?0???
?0?1?
01?10
10 10
0000000000
0000000000
0000000000

出力例 1

11010
1011001
0100000000

1 番目のテストケースについて、S_x = \lbrace 1,3 \rbrace , S_y = \lbrace 1,5 \rbrace , S_z = \lbrace 3,7 \rbrace になります。 k = 0,1,3 について、

• f(3, 1, 3) \equiv 0 \pmod{M} ： 条件を満たす (a,b,c) の組は存在しません。

• f(1, 1, 3) \equiv 1 \pmod{M} ： 条件を満たす (a,b,c) は (1,1,1) の 1 つです。

• f(1, 5, 7) \equiv 3 \pmod{M} ： 条件を満たす (a,b,c) は (1,1,5) , (1,5,1) , (5,1,1) の 3 つです。

のように条件を満たす (x,y,z) が存在することがわかります。

一方、 k = 2,4 について条件を満たすような (x,y,z) は存在しません。