Byteasar 在数学课上表现不佳，作为惩罚，他需要计算一个具有 $n$ 个整数系数的长多项式 $W$： $$W(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-2}x^{n-2} + a_{n-1}x^{n-1}$$ 在点 $q^1, q^2, \dots, q^n$ 处的值。为了帮助老师快速验证结果，Byteasar 需要首先提供这些值之和对 $m$ 取模的余数，然后提供所有这些值分别对 $m$ 取模的余数。

Byteasar 不仅经常表现不佳，而且相当懒惰，所以他在去参加聚会前（出奇礼貌地）请求你帮忙完成这项任务。值得称赞的是，Byteasar 非常聪明，只是太懒了，没有去实现他的想法。在告别时，他分享了他的直觉，认为以下性质可以大幅减少计算结果所需的计算量：$n$ 是 2 的幂，且 $q^n$ 对 $m$ 取模的余数为 1（即 $q^n \pmod m = 1$）。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $q$（$n \ge 1$，$n$ 是 2 的幂，$2 \le m \le 10^9$，$1 \le q < m$，$q^n \pmod m = 1$），由空格分隔。

第二行包含一个由 $n$ 个整数组成的序列，由空格分隔，按顺序指定多项式的系数：$a_0, a_1, \dots, a_{n-1}$（$0 \le a_i \le 10^9$）。

输出格式

第一行应输出一个整数，即多项式 $W$ 在点 $q^1, q^2, q^3, \dots, q^n$ 处的值之和对 $m$ 取模的余数。第二行应输出 $W(q^1), W(q^2), W(q^3), \dots, W(q^n)$ 分别对 $m$ 取模的余数，由空格分隔。

样例

样例输入 1

4 13 5
3 2 2 1

样例输出 1

12
6 2 9 8

说明

对于样例：多项式为 $W(x) = 3 + 2x + 2x^2 + x^3$，因此它在各点的值分别为 $W(5) = 188$，$W(5^2) = 16\,928$，$W(5^3) = 1\,984\,628$，$W(5^4) = 244\,923\,128$。第一行输出的数字是 $188 + 16\,928 + 1\,984\,628 + 244\,923\,128 = 246\,924\,872$ 对 13 取模的余数，即 12。第二行提供了上述各项对 13 取模的余数。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试点。

如果总和的余数正确，但其中一个后续值不正确，只要第二行中的所有 $n$ 个数字都在 $0$ 到 $m-1$ 的范围内，你的程序将获得该测试点最高 40% 的分数。