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 翻译