← 返回题目列表

Codeforces · 453/D

D. 小马驹和和谐元素

中文机器翻译题面 查看原题

和谐元素是代表和谐主观方面的六件超自然文物。他们可以说是小马国最强大的力量。 《Elements of Harmony》的内部可以看作是一个完整的图,其中 n 个顶点标记为 0 到 n - 1,其中 n 是 2 的幂,等于 2m。

和谐元素中的能量处于不断运动之中。根据古书,顶点u在时间i(ei[u])的能量等于:

$$e_i[u] = \sum_v e_{i-1}[v] \cdot b[f(u,v)]$$

这里 b[] 是变换系数 — m + 1 个整数的数组,f(u, v) 是数字 (u xor v) 的二进制表示形式中 1 的数量。

给定变换系数和时间 0 (e0[]) 处的能量分布。帮助 Twilight Sparkle 预测时间 t (et[]) 的能量分布。答案可能相当大,因此输出它对 p 取模。

输入

第一行包含三个整数 m、t 和 p (1 ≤ m ≤ 20;0 ≤ t ≤ 1018;2 ≤ p ≤ 109)。以下行包含 n (n = 2m) 个整数 e0[i] (1 ≤ e0[i] ≤ 109; 0 ≤ i < n)。下一行包含 m + 1 个整数 b[i] (0 ≤ b[i] ≤ 109; 0 ≤ i ≤ m)。

输出

输出 n 行,第 i 行必须包含单个整数 et[i] 模 p。

示例

输入 #1

2 2 10000
4 1 2 3
0 1 0

输出 #1

14
6
6
14