Background

This is a template problem, with no background.

Problem Description

Given a degree $n$ falling factorial polynomial $A(x)$ and a degree $m$ falling factorial polynomial $B(x)$, you need to compute a degree $n+m$ falling factorial polynomial $F(x)$ such that $F(x)=A(x)B(x)$.

Since the result can be very large, output the coefficients of the polynomial modulo $998244353$.

Input Format

The first line contains two positive integers $n,m$, representing the degrees of the falling factorial polynomials.

The second line contains $n+1$ non-negative integers $a_0,a_1,a_2,\dots,a_n$, representing the coefficients of $A(x)$. That is, $A(x)=a_0+a_1x+a_2x^{\underline 2}+\dots+a_nx^{\underline n}$.

The third line contains $m+1$ non-negative integers $b_0,b_1,b_2,\dots,b_m$, representing the coefficients of $B(x)$. That is, $B(x)=b_0+b_1x+b_2x^{\underline 2}+\dots+b_mx^{\underline m}$.

Output Format

Output one line with $n+m+1$ non-negative integers, representing the coefficients of $F(x)$ modulo $998244353$.

2 3
1 2 3
1 2 3 4

1 8 52 148 89 12

Hint

For $20\%$ of the testdata, $n,m\leqslant 1000$.

For $100\%$ of the testdata, $1\leqslant n,m\leqslant 10^5$, $a_i,b_i\in[0,998244353)$, and $a_n,b_m \neq 0$.

$x^{\underline n}=\left\{\begin{matrix}1 & n=0\\ x\times (x-1)^{\underline{n-1}} & n\geqslant 1 \end{matrix}\right.$

$\sum\limits_{i=0}^n a_ix^{\underline i},a_n\neq 0$ is a degree $n$ falling factorial polynomial in $x$.

It is easy to prove that a degree $n$ falling factorial polynomial uniquely determines a degree $n$ polynomial. Therefore, the definition of the product of falling factorial polynomials is: take the product of the corresponding polynomials, and then convert it back to the corresponding falling factorial polynomial.

Translated by ChatGPT 5