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 后得到的二进制字符串所代表的所有整数构成集合 $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$，并且 $f(x, y, z) \equiv k \pmod{M}$ 的三元组 $(x, y, z)$。

给定 $T$ 个测试用例，请分别解决。

输入按以下格式给出。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例格式如下：

$N\ M$
$X$
$Y$
$Z$

请输出 $T$ 行。第 $i$ 行对于第 $i$ 个测试用例，依次输出 $k=0,1,\ldots,M-1$，如果存在满足 $f(x, y, z) \equiv k \pmod{M}$ 的 $(x, y, z)$，则对应位置输出 1，否则输出 0。

样例解释 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)$。
• $f(1, 5, 7) \equiv 3 \pmod{M}$ ：满足条件的 $(a, b, c)$ 有 $(1,1,5), (1,5,1), (5,1,1)$ 共 $3$ 个。

因此，对于 $k = 0, 1, 3$，存在符合条件的三元组。在 $k = 2,4$ 时，不存在符合条件的 $(x, y, z)$。

数据范围

• $1 \leq T \leq 3000$
• $1 \leq N \leq 3000$
• $1 \leq M \leq 10^6$
• $X, Y, Z$ 均为长度为 $N$ 的仅包含 0、1、? 的字符串
• 所有测试用例中 $N$ 的总和不超过 $3000$
• 所有测试用例中 $M$ 的总和不超过 $10^6$
• $N, M$ 均为整数

由 ChatGPT 5 翻译