题目描述Description

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

输入格式Input

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

每组数据的第一行包含 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.

输出格式Output

对于每组数据，输出 n 个整数，表示 f(w^0), f(w^1), \dots, f(w^{n - 1}) 除以 p 的余数.

样例Sample

出题Author

ftiasch

来源Source

湖南省第十六届大学生计算机程序设计竞赛（HNCPC2020）