Background

One day, NaCly_Fish saw $\mathsf r \color{red} \mathsf{qy}$ say in the group chat: “I finally finished writing polynomial composition! qwq”.
So she curiously asked $\mathsf r \color{red} \mathsf{qy}$: “How do you write this thing?”.

$\mathsf r \color{red} \mathsf{qy}$ only threw her a PDF in “Yingwen” (pinyin), but she could not understand it at all.
So she asked you for help, hoping you can help her solve this difficult problem.

Problem 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