$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$인 모든 $i$에 대하여 $w^i \not\equiv 1 \pmod p$이다.

$w$를 선택하는 방법은 여러 가지가 있을 수 있으므로 DFT는 유일하지 않다. 이 문제에서는 다음과 같이 유일하게 결정한다. $g$를 법 $p$에 대한 생성원(generator)이라 하자. 즉, $0 < x < p$인 모든 $x$에 대하여 $0 \le r < p-1$인 양의 정수 $r$이 존재하여 $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{ times}}$로 정의하며, 당신의 과제는 $\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)$