令 $p$ 為一個質數，且 $a = (a_0, a_1, \dots, a_{n-1})$ 為一個包含 $n$ 個整數的陣列，其中 $p = Kn + 1$，且 $K$ 為某個正整數。我們稱陣列 $\hat{a} = (\hat{a}_0, \hat{a}_1, \dots, \hat{a}_{n-1})$ 為陣列 $a$ 的離散傅立葉轉換（Discrete Fourier Transform），若對於每個 $k = 0, 1, \dots, n-1$ 皆滿足下列式子：
$$\hat{a}_k = \left( \sum_{j=0}^{n-1} a_j w^{jk} \right) \pmod p$$
我們簡記為 $\hat{a} = \text{DFT}(a)$。這裡 $w$ 代表模 $p$ 下的一個本原 $n$ 次單位根，亦即滿足 $w^n \equiv 1 \pmod p$，且對於每個 $0 < i < n$ 皆有 $w^i \not\equiv 1 \pmod p$。
請注意，$w$ 可能有多種選擇，因此 DFT 並非唯一。讓我們釐清本題中如何唯一地決定它。令 $g$ 為模 $p$ 的一個生成元（generator），亦即對於每個 $0 < x < p$，皆存在一個正整數 $r$ 滿足 $0 \le r < p-1$ 且 $x \equiv g^r \pmod p$。你可以找到滿足條件的最小正整數 $g$，並選擇 $w = g^K \pmod p$。
現在我們定義 $\text{DFT}^{(m)}(a) = \underbrace{\text{DFT}(\text{DFT}(\dots \text{DFT}(a)\dots))}_{m \text{ 次}}$，你的任務就是求出 $\text{DFT}^{(m)}(a)$。
輸入格式
第一行包含三個以空白分隔的整數：$n$ ($2 \le n \le 3 \cdot 10^5$)、$p$ ($5 \le p \le 10^9+7$) 以及 $m$ ($0 \le m \le 10^{18}$)，為上述問題的參數。保證 $p$ 為質數且 $n$ 整除 $p-1$。
第二行包含 $n$ 個以空白分隔的整數 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < p$)，即陣列 $a$。
輸出格式
輸出 $n$ 個以空白分隔的整數 $a'_0, a'_1, \dots, a'_{n-1}$，即經過題目所述運算後的結果陣列。
範例
輸入 1
6 61 4 24 17 39 52 25 7
輸出 1
10 2 1 42 46 8
說明
在範例測資中，對於 $p = 61$，最小的生成元為 $g = 2$。我們有 $K = \frac{61-1}{6} = 10$，因此我們選擇 $w = 2^{10} \pmod{61} = 48$ 作為模 $61$ 下的本原 $6$ 次單位根。DFT 的前幾次迭代如下：
- $\text{DFT}^{(0)}(a) = (24, 17, 39, 52, 25, 7)$
- $\text{DFT}^{(1)}(a) = (42, 55, 25, 12, 39, 32)$
- $\text{DFT}^{(2)}(a) = (22, 42, 28, 7, 51, 41)$
- $\text{DFT}^{(3)}(a) = (8, 9, 51, 11, 28, 25)$
- $\text{DFT}^{(4)}(a) = (10, 2, 1, 42, 46, 8)$