Description

Given an $n$-degree polynomial $F(x)$ and an $m$-degree polynomial $G(x)$, find polynomials $Q(x)$ and $R(x)$ such that:

• $\deg Q(x) = n - m$, and $\deg R(x) < m$.
• $F(x) = Q(x) * G(x) + R(x)$.

All operations are performed modulo $998244353$.

Input Format

The first line contains two integers $n$ and $m$, as described above.
The second line contains $n+1$ integers, giving the coefficients of $F(x)$ from low to high degree.
The third line contains $m+1$ integers, giving the coefficients of $G(x)$ from low to high degree.

Output Format

The first line contains $n - m + 1$ integers, giving the coefficients of $Q(x)$ from low to high degree.
The second line contains $m$ integers, giving the coefficients of $R(x)$ from low to high degree.
If $\deg R(x) < m - 1$, pad the remaining coefficients with $0$.

5 1
1 9 2 6 0 8
1 7

237340659 335104102 649004347 448191342 855638018
760903695

Hint

For all testdata, $1 \le m < n \le 10^5$, and the given coefficients belong to $[0, 998244353) \cap \mathbb{Z}$.

Translated by ChatGPT 5