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