AT_KeioPC2025_o Three Constraints

非負整数 $ 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 $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N\ M $ $ X $ $ Y $ $ Z $

$ T $ 行出力せよ。 $ i $ 行目には $ \mathrm{case}_i $ について、 $ k = 0, 1, \ldots, M-1 $ の順に $ f(x, y, z) \equiv k \pmod{M} $ なる $ (x,y,z) $ が存在するならば `1` 、そうでないならば `0` を出力せよ。

### Sample Explanation 1 $ 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) $ は存在しません。 ### Constraints - $ 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 $ は整数