$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 < k < n$ を満たすすべての $k$ に対して $w^k \not\equiv 1 \pmod p$ である。
$w$ の選び方は複数存在し得るため、DFT は一意ではない。本問題では、以下のようにして一意に定める。$g$ を法 $p$ における原始根とする。すなわち、$0 < x < p$ を満たすすべての $x$ に対して、$x \equiv g^r \pmod p$ となるような $0 \le r < p-1$ が存在する。この条件を満たす最小の正の整数 $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)$ を求めることである。
入力
1 行目には、3 つの整数 $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$ を割り切ることが保証されている。
2 行目には、$n$ 個の整数 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < p$) が空白区切りで与えられる。
出力
問題で指定された操作を行った後の結果である $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)$