Пусть $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})$ является дискретным преобразованием Фурье (Discrete Fourier Transform) массива $a$, если для каждого $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$ обозначает примитивный $n$-й корень из единицы по модулю $p$, то есть $w^n \equiv 1 \pmod p$ и для любого $i$ такого, что $0 < i < n$, $w^i \not\equiv 1 \pmod p$.
Заметим, что может быть несколько вариантов выбора $w$, поэтому DFT не будет единственным. Уточним, как однозначно найти его для этой задачи. Пусть $g$ — первообразный корень по модулю $p$, то есть для любого $x$ такого, что $0 < x < p$, существует положительное целое число $r$ такое, что $0 \le r < p-1$ и $x = 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{ раз}}$, поэтому ваша задача — просто найти $\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$ в качестве примитивного 6-го корня из единицы по модулю 61. Первые итерации 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)$