Description

Given an $n$-degree polynomial $F(x)$ and an $m$-degree polynomial $G(x)$, you need to find an $n$-degree polynomial $H(x)$ that satisfies:

$$H(x) \equiv F(G(x))\space (\text{mod }x^{n+1})$$

In other words, the polynomial you need should satisfy:

$$H(x) \equiv \sum\limits_{i=0}^n [x^i]F(x)\times G(x)^i \space (\text{mod }x^{n+1})$$

Take all coefficients of the result modulo $998244353$.

Input Format

The first line contains two positive integers $n,m$, representing the degrees of $F(x)$ and $G(x)$.
The second line contains $n+1$ non-negative integers $f_i$, representing the coefficient of the $x^i$ term of $F(x)$.
The third line contains $m+1$ non-negative integers $g_i$, representing the coefficient of the $x^i$ term of $G(x)$.

Output Format

Output one line with $n+1$ non-negative integers, from low degree to high degree, representing the coefficients of $H(x)$.

5 1
1 9 2 6 0 8
1 7

26 497 4900 29498 96040 134456 

Hint

Constraints:
$1\le m \le n \le 20000$
$f_i,g_i \in [0,998244353)\cap \mathbb Z$

Translated by ChatGPT 5