1095 : 抄板子

Description

Bobo 有一个 (n − 1) 次多项式 $f(x) = \sum_{i = 0}^n a_i x^i$ 和一个质数 p, 还有一个整数 w. 他想求出 f(w⁰), f(w¹), …, f(w^n − 1) 除以 p 的余数.

Input

输入文件包含多组数据，请处理到文件结束。

每组数据的第一行包含 3 个整数 n, p 和 w. 第二行包含 n 个整数 a₀, …, a_n − 1.

• 3 ≤ n ≤ 2 × 10⁵
• 存在一个非负整数 k 使得 n = 3 × 2^k.
• 2 ≤ p ≤ 10⁹, p 是质数
• n 是 (p − 1) 的约数
• 1 ≤ w < p
• wⁿ mod p = 1
• 0 ≤ a_i < p
• n 的和不超过 5 × 10⁵.

Output

对于每组数据，输出 n 个整数，表示 f(w⁰), f(w¹), …, f(w^n − 1) 除以 p 的余数.

Sample

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

Hint

Source

Author

ftiasch