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 $ 回目の操作では、 $ \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 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります（ $ 2 $ 進表記すると $ 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 $ 行に出力せよ。

### Sample Explanation 1 $ 1 $ 回目の操作では、 $ A_3,A_5,A_6 $ が $ 1\times 4\bmod 100=4 $ になります。 $ 2 $ 回目の操作では、 $ A_3 $ が $ 4\times 25 \bmod 100=0 $ になります。 ### Constraints - 入力は全て整数 - $ 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 $