P4245 [Template] Polynomial Multiplication with Arbitrary Modulus

Template problem, no background.

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$.

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 $n+m+1$ integers. The $i$-th integer $c_i$ denotes the coefficient of the $(i-1)$-th term of $F(x) * G(x)$.

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