题目描述

这是一道模板题。

给数列 $a_0, \dots, a_n, b_0, \dots, b_m$ 和正整数 $M$，求数列 $c0, \dots, c{n+m}$，满足：

$$ ck = \sum{i=\max(k-m,0)}^{\min(k,n)} \binom k i ai b{k-i} \bmod M $$

其中 $\binom k i = \frac{k!}{i!(k-i)!}$ 是组合数。

输入格式

第一行输入三个正整数 $n, m, M$。

接下来一行输入 $n + 1$ 个整数 $a_0, \dots, a_n$。

接下来一行输入 $m + 1$ 个整数 $b_0, \dots, b_m$。

输出格式

输出一行 $n + m + 1$ 个数，依次输出 $c_0, c1, \dots, c{n+m}$。

样例

input

2 5 114
5 1 4
1 9 1 9 8 10

output

5 46 27 42 100 108 84 42

取模前的数列是 $[5, 46, 27, 156, 100, 450, 540, 840]$。

数据范围与提示

对于 $10\%$ 的数据，保证 $n,m\le 10^3$。

对于另外 $20\%$ 的数据，保证 $M$ 是质数。

对于另外 $20\%$ 的数据，保证 $M$ 是 $2$ 的幂。

对于 $100\%$ 的数据，保证 $0\le n, m\le 10^5, 2\le M\le 10^9, 0\le a_i, b_j < M$。