#4671. 模板. 二项卷积

模板. 二项卷积

Description

这是一道模板题。

给数列 a0,,an,b0,,bma_0, \dots, a_n, b_0, \dots, b_m 和正整数 MM,求数列 c0,,cn+mc_0, \dots, c_{n+m},满足:

$$c_k = \sum_{i=\max(k-m,0)}^{\min(k,n)} \binom k i a_i b_{k-i} \bmod M $$

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

Input

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

接下来一行输入 n+1n + 1 个整数 a0,,ana_0, \dots, a_n

接下来一行输入 m+1m + 1 个整数 b0,,bmb_0, \dots, b_m

Output

输出一行 n+m+1n + m + 1 个数,依次输出 c0,c1,,cn+mc_0, c_1, \dots, c_{n+m}

Samples

2 5 114
5 1 4
1 9 1 9 8 10
5 46 27 42 100 108 84 42

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

Limitation

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

对于另外 20%20\% 的数据,保证 MM 是质数。

对于另外 20%20\% 的数据,保证 MM22 的幂。

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