AT_utpc2023_c Contour Multiplication

有一个长度为 $2^N$ 的数列 $(A_0, A_1, \dots, A_{2^N-1})$，初始时 $A_0=A_1=\dots=A_{2^N-1}=1$。 有 $K$ 次操作。第 $i$ 次操作，会令所有满足 $\mathrm{popcount}(j \oplus C_i) = D_i$ 的 $j \ (0 \leq j < 2^N)$，将 $A_j$ 替换为 $(A_j \times X_i)\bmod M$。 请输出经过所有操作之后的 $A_0, A_1, \dots, A_{2^N-1}$。 其中，$\mathrm{popcount}(X)$ 表示非负整数 $X$ 的二进制表示中 $1$ 的个数。 位运算 $\mathrm{XOR}$（$\oplus$）对非负整数 $A, B$ 的定义为：将 $A$ 和 $B$ 的二进制表示对应位进行异或操作，得到的第 $2^k$ 位为 $A$ 和 $B$ 的该位若只有一个为 $1$ 则为 $1$，否则为 $0$。 例如：$3 \oplus 5 = 6$，因二进制 $011 \oplus 101 = 110$。

输入按以下格式从标准输入给出： > $N$ $M$ $K$ > $C_1$ $D_1$ $X_1$ > $C_2$ $D_2$ $X_2$ > $\vdots$ > $C_K$ $D_K$ $X_K$

请将 $A_0, A_1, \dots, A_{2^N-1}$ 以空格分隔，输出在一行中。

### 样例解释 1 第 $1$ 次操作，$A_3, A_5, A_6$ 都会变为 $1\times 4\bmod 100=4$。 第 $2$ 次操作，$A_3$ 会被变为 $4\times 25 \bmod 100=0$。 ### 数据范围 - 所有输入均为整数。 - $1 \leq N \leq 18$ - $2 \leq M \leq 10^9$ - $1 \leq K \leq 5\times 10^5$ - $0 \leq C_i < 2^N$ - $0 \leq D_i \leq N$ - $2 \leq X_i \leq 10^9$ 由 ChatGPT 5 翻译