设 $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) \bmod p$$
我们简记为 $\hat{a} = \text{DFT}(a)$。这里 $w$ 表示模 $p$ 下的一个本原 $n$ 次单位根，即满足 $w^n \equiv 1 \pmod p$，且对于每个满足 $0 < i < n$ 的 $i$，都有 $w^i \not\equiv 1 \pmod p$。
注意，$w$ 可能有多种选择，因此 DFT 并不唯一。让我们明确本题中如何唯一确定它。设 $g$ 为模 $p$ 的一个原根，即对于每个满足 $0 < x < p$ 的 $x$，都存在一个正整数 $r$ 满足 $0 \le r < p-1$ 且 $x \equiv g^r \pmod p$。你可以找到满足条件的最小正整数 $g$，并选择 $w = g^K \bmod 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} \bmod 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)$