Bobo has a polynomial $f(x) = \sum_{i = 0}^{n - 1} a_i x^i$ of degree $(n - 1)$, a prime number $p$, and an integer $w$. He wants to find the remainders of $f(w^0), f(w^1), \dots, f(w^{n - 1})$ when divided by $p$.

Input

The input file contains multiple test cases. Process until the end of the file.

Each test case consists of three integers $n$, $p$, and $w$ on the first line. The second line contains $n$ integers $a_0, \dots, a_{n - 1}$.

• $3 \leq n \leq 2 \times 10^5$
• There exists a non-negative integer $k$ such that $n = 3 \times 2^k$.
• $2 \leq p \leq 10^9$, $p$ is a prime number.
• $n$ is a divisor of $(p - 1)$.
• $1 \leq w < p$
• $w^n \bmod p = 1$
• $0 \leq a_i < p$
• The sum of $n$ over all test cases does not exceed $5 \times 10^5$.

Output

For each test case, output $n$ integers representing the remainders of $f(w^0), f(w^1), \dots, f(w^{n - 1})$ when divided by $p$.

Examples

Input 1

3 7 1
1 2 3
3 7 2
1 2 3
6 458719 458718
91633 324072 357282 141401 443440 75350

Output 1

6 6 6
6 3 1
57021 351532 57021 351532 57021 351532