Bobo 有一个 $(n - 1)$ 次多项式 $f(x) = \sum_{i = 0}^{n - 1} a_i x^i$ 和一个质数 $p$, 还有一个整数 $w$. 他想求出 $f(w^0), f(w^1), \dots, f(w^{n - 1})$ 除以 $p$ 的余数.
输入格式
输入文件包含多组数据，请处理到文件结束。
每组数据的第一行包含 $3$ 个整数 $n$, $p$ 和 $w$. 第二行包含 $n$ 个整数 $a_0, \dots, a_{n - 1}$.
- $3 \leq n \leq 2 \times 10^5$
- 存在一个非负整数 $k$ 使得 $n = 3 \times 2^k$.
- $2 \leq p \leq 10^9$, $p$ 是质数
- $n$ 是 $(p - 1)$ 的约数
- $1 \leq w < p$
- $w^n \bmod p = 1$
- $0 \leq a_i < p$
- $n$ 的和不超过 $5 \times 10^5$.
输出格式
对于每组数据，输出 $n$ 个整数，表示 $f(w^0), f(w^1), \dots, f(w^{n - 1})$ 除以 $p$ 的余数.
样例输入
3 7 1 1 2 3 3 7 2 1 2 3 6 458719 458718 91633 324072 357282 141401 443440 75350
样例输出
6 6 6 6 3 1 57021 351532 57021 351532 57021 351532