Cho $p$ là một số nguyên tố và $a = (a_0, a_1, \dots, a_{n-1})$ là một mảng gồm $n$ số nguyên, trong đó $p = Kn + 1$ với một số nguyên dương $K$ nào đó. Ta nói mảng $\hat{a} = (\hat{a}_0, \hat{a}_1, \dots, \hat{a}_{n-1})$ là Biến đổi Fourier rời rạc (Discrete Fourier Transform) của mảng $a$ nếu với mọi $k = 0, 1, \dots, n-1$ ta có:

$$\hat{a}_k = \left( \sum_{j=0}^{n-1} a_j w^{jk} \right) \pmod p$$

và ta viết đơn giản là $\hat{a} = \text{DFT}(a)$. Ở đây $w$ ký hiệu một căn bậc $n$ nguyên thủy của đơn vị modulo $p$, nghĩa là ta có $w^n \equiv 1 \pmod p$ và với mọi $i$ sao cho $0 < i < n$, $w^i \not\equiv 1 \pmod p$.

Lưu ý rằng có thể có nhiều lựa chọn cho $w$, vì vậy DFT sẽ không duy nhất. Hãy làm rõ cách xác định duy nhất nó cho bài toán này. Gọi $g$ là một phần tử sinh modulo $p$, nghĩa là với mọi $x$ sao cho $0 < x < p$, tồn tại một số nguyên dương $r$ sao cho $0 \le r < p-1$ và $x = g^r \pmod p$. Bạn có thể tìm giá trị dương nhỏ nhất cho $g$ thỏa mãn điều kiện này và chọn $w = g^K \pmod p$.

Bây giờ ta định nghĩa $\text{DFT}^{(m)}(a) = \underbrace{\text{DFT}(\text{DFT}(\dots \text{DFT}(a)\dots))}_{m \text{ lần}}$, vì vậy nhiệm vụ của bạn chỉ là tìm $\text{DFT}^{(m)}(a)$.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách: $n$ ($2 \le n \le 3 \cdot 10^5$), $p$ ($5 \le p \le 10^9+7$), và $m$ ($0 \le m \le 10^{18}$), là các tham số của bài toán được mô tả ở trên. Đảm bảo rằng $p$ là số nguyên tố và $n$ chia hết $p-1$.

Dòng thứ hai chứa $n$ số nguyên cách nhau bởi dấu cách $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < p$), là mảng $a$.

Dữ liệu ra

In ra $n$ số nguyên cách nhau bởi dấu cách $a'_0, a'_1, \dots, a'_{n-1}$, là mảng kết quả sau khi thực hiện phép toán đã nêu trong bài toán.

Ví dụ

Dữ liệu vào 1

6 61 4
24 17 39 52 25 7

Dữ liệu ra 1

10 2 1 42 46 8

Ghi chú

Trong trường hợp kiểm thử mẫu, phần tử sinh nhỏ nhất cho $p = 61$ là $g = 2$. Ta có $K = \frac{61-1}{6} = 10$, vì vậy ta chọn $w = 2^{10} \pmod{61} = 48$ là căn bậc 6 nguyên thủy của đơn vị modulo 61. Các lần lặp đầu tiên của DFT như sau:

• $\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)$