Niech $p$ będzie liczbą pierwszą, a $a = (a_0, a_1, \dots, a_{n-1})$ tablicą $n$ liczb całkowitych, gdzie $p = Kn + 1$ dla pewnej liczby całkowitej dodatniej $K$. Mówimy, że tablica $\hat{a} = (\hat{a}_0, \hat{a}_1, \dots, \hat{a}_{n-1})$ jest dyskretną transformatą Fouriera (DFT) tablicy $a$, jeśli dla każdego $k = 0, 1, \dots, n-1$ zachodzi:

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

Zapisujemy to po prostu jako $\hat{a} = \text{DFT}(a)$. Tutaj $w$ oznacza pierwotny $n$-ty pierwiastek z jedynki modulo $p$, to znaczy, że $w^n \equiv 1 \pmod p$ oraz dla każdego $i$ takiego, że $0 < i < n$, $w^i \not\equiv 1 \pmod p$.

Zauważ, że może istnieć wiele wyborów $w$, więc DFT nie będzie jednoznaczna. Wyjaśnijmy, jak wyznaczyć ją jednoznacznie w tym zadaniu. Niech $g$ będzie generatorem modulo $p$, to znaczy, że dla każdego $x$ takiego, że $0 < x < p$, istnieje liczba całkowita dodatnia $r$ taka, że $0 \le r < p-1$ oraz $x = g^r \bmod p$. Możesz znaleźć najmniejszą dodatnią wartość $g$, która spełnia ten warunek i wybrać $w = g^K \bmod p$.

Definiujemy $\text{DFT}^{(m)}(a) = \underbrace{\text{DFT}(\text{DFT}(\dots \text{DFT}(a)\dots))}_{m \text{ razy}}$, więc Twoim zadaniem jest po prostu znalezienie $\text{DFT}^{(m)}(a)$.

Wejście

W pierwszej linii znajdują się trzy liczby całkowite oddzielone spacjami: $n$ ($2 \le n \le 3 \cdot 10^5$), $p$ ($5 \le p \le 10^9+7$) oraz $m$ ($0 \le m \le 10^{18}$), parametry problemu opisanego powyżej. Gwarantuje się, że $p$ jest liczbą pierwszą oraz że $n$ dzieli $p-1$ bez reszty.

W drugiej linii znajduje się $n$ liczb całkowitych oddzielonych spacjami $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < p$), tablica $a$.

Wyjście

Wypisz $n$ liczb całkowitych oddzielonych spacjami $a'_0, a'_1, \dots, a'_{n-1}$, będących wynikową tablicą po wykonaniu operacji określonej w zadaniu.

Przykład

Wejście 1

6 61 4
24 17 39 52 25 7

Wyjście 1

10 2 1 42 46 8

Uwagi

W przykładowym teście najmniejszym możliwym generatorem dla $p = 61$ jest $g = 2$. Mamy $K = \frac{61-1}{6} = 10$, więc wybieramy $w = 2^{10} \bmod 61 = 48$ jako pierwotny 6-ty pierwiastek z jedynki modulo 61. Pierwsze iteracje DFT wyglądają następująco:

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