Description

Given $2$ polynomials $F(x), G(x)$, compute $F(x) * G(x)$. The coefficients are taken modulo $p$, and it is not guaranteed that $p$ can be written in the form $p = a \cdot 2^k + 1$.

Input Format

The input consists of $3$ lines.
The first line contains $3$ integers $n, m, p$, representing the degrees of $F(x)$ and $G(x)$, and the modulus $p$.
The second line contains $n+1$ integers; the $i$-th integer $a_i$ denotes the coefficient of the $(i-1)$-th term of $F(x)$.
The third line contains $m+1$ integers; the $i$-th integer $b_i$ denotes the coefficient of the $(i-1)$-th term of $G(x)$.

Output Format

Output $n+m+1$ integers. The $i$-th integer $c_i$ denotes the coefficient of the $(i-1)$-th term of $F(x) * G(x)$.

5 8 28
19 32 0 182 99 95
77 54 15 3 98 66 21 20 38

7 18 25 19 5 13 12 2 9 22 5 27 6 26

Hint

For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $0 \leq a_i, b_i \leq 10^9$, $2 \leq p \leq 10^9 + 9$.

Translated by ChatGPT 5