配点 : 100 点
問題文
长度 小于或等于 2^N 序列 使用 (A_0, A_1, \dots, A_{2^N-1}) 。最初,A_0=A_1=\dots=A_{2^N-1}=1 。
K 操作。i 次操作中,\text{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 反对 \text{popcount}(X) 是什么? 表示 X 该值应乘以 2 当用进制表示时 1 的个数,即 2^k 的位是 1 的非负整数 k 的号码。
位单位 \mathrm{XOR} 演算 \oplus 是什么? 表示
非負整数 A, B 按位 \mathrm{XOR}、A \oplus B 定义如下。 当
- A \oplus B 该值应乘以 2 用进制表示时的 2^k (k \geq 0) 中的位数为A, B 该值应乘以 2 用进制表示时的 2^k 数字中只有一位是 1 如果 1,否则 输出为 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
入力
输入是按以下格式从标准输入给出的。
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
3 100 2 0 2 4 3 0 25
出力例 1
1 1 1 0 1 4 4 1
1 次操作中,A_3,A_5,A_6 是 在 1\times 4\bmod 100=4 。
2 次操作中,A_3 是 在 4\times 25 \bmod 100=0 。
入力例 2
4 998244353 7 0 2 4 3 0 25 9 4 37 4 1 16 6 3 8 1 4 68 13 3 97
出力例 2
1552 8 1 9700 1 64 229696 1 8 4 388 8 64 8 68 1