Sea $p$ un número primo y $a = (a_0, a_1, \dots, a_{n-1})$ un arreglo de $n$ enteros, donde $p = Kn + 1$ para algún entero positivo $K$. Decimos que el arreglo $\hat{a} = (\hat{a}_0, \hat{a}_1, \dots, \hat{a}_{n-1})$ es la Transformada Discreta de Fourier del arreglo $a$ si para todo $k = 0, 1, \dots, n-1$ se cumple lo siguiente:
$$\hat{a}_k = \left( \sum_{j=0}^{n-1} a_j w^{jk} \right) \pmod p$$
y simplemente escribimos $\hat{a} = \text{DFT}(a)$. Aquí $w$ denota una raíz primitiva $n$-ésima de la unidad módulo $p$, es decir, tenemos $w^n \equiv 1 \pmod p$ y, para todo $i$ tal que $0 < i < n$, $w^i \not\equiv 1 \pmod p$.
Tenga en cuenta que puede haber múltiples opciones para $w$, por lo que la DFT no será única. Aclaremos cómo encontrarla de forma única para este problema. Sea $g$ un generador módulo $p$, es decir, para todo $x$ tal que $0 < x < p$, existe un entero positivo $r$ tal que $0 \le r < p-1$ y $x = g^r \pmod p$. Puede encontrar el valor positivo más pequeño para $g$ que funcione y elegir $w = g^K \pmod p$.
Ahora definimos $\text{DFT}^{(m)}(a) = \underbrace{\text{DFT}(\text{DFT}(\dots \text{DFT}(a)\dots))}_{m \text{ veces}}$, por lo que su tarea es simplemente encontrar $\text{DFT}^{(m)}(a)$.
Entrada
La primera línea contiene tres enteros separados por espacios: $n$ ($2 \le n \le 3 \cdot 10^5$), $p$ ($5 \le p \le 10^9+7$) y $m$ ($0 \le m \le 10^{18}$), los parámetros del problema descrito anteriormente. Se garantiza que $p$ es primo y que $n$ divide a $p-1$ exactamente.
La segunda línea contiene $n$ enteros separados por espacios $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < p$), el arreglo $a$.
Salida
Imprima $n$ enteros separados por espacios $a'_0, a'_1, \dots, a'_{n-1}$, el arreglo resultante después de realizar la operación indicada en el problema.
Ejemplos
Entrada 1
6 61 4 24 17 39 52 25 7
Salida 1
10 2 1 42 46 8
Nota
En el caso de prueba de ejemplo, el generador más pequeño posible para $p = 61$ es $g = 2$. Tenemos que $K = \frac{61-1}{6} = 10$, por lo que elegimos $w = 2^{10} \pmod{61} = 48$ para ser la raíz primitiva 6-ésima de la unidad módulo 61. Las primeras iteraciones de la DFT son las siguientes:
- $\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)$