有一个长度为 $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 \le j < 2^N$），将 $A_j$ 替换为 $(A_j \times X_i) \pmod M$。

在执行完所有操作后，确定 $A_0, A_1, \dots, A_{2^N-1}$ 的值。

输入格式

输入通过标准输入给出，格式如下：

$N \ M \ K$ $C_1 \ D_1 \ X_1$ $C_2 \ D_2 \ X_2$ $\vdots$ $C_K \ D_K \ X_K$

• 所有输入值均为整数。
• $1 \le N \le 18$
• $2 \le M \le 10^9$
• $1 \le K \le 5 \times 10^5$
• $0 \le C_i < 2^N$
• $1 \le D_i \le N$
• $2 \le X_i \le 10^9$

输出格式

在执行完所有操作后，输出 $A_0, A_1, \dots, A_{2^N-1}$ 的值，在一行中以空格分隔。

样例

输入格式 1

3 100 2
0 2 4
3 0 25

输出格式 1

1 1 1 0 1 4 4 1

输入格式 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