题目描述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

出题Author

ftiasch

来源Source