Background

Compared with P5373, this problem has larger constraints.

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_{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$, which are the degrees of $F(x)$ and $G(x)$, respectively.

The second line contains $n+1$ non-negative integers $f_i$, where $f_i$ is the coefficient of the $i$-th power term of $F(x)$.

The third line contains $m+1$ non-negative integers $g_i$, where $g_i$ is the coefficient of the $i$-th power term of $G(x)$.

Output Format

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

4 3
1 2 3 4 5
1 2 3 4

15 80 300 892 2069

Hint

Constraints:

• $1\le m \le n \le 200000$
• $f_i,g_i \in [0,998244353)\cap \mathbb Z$

Test Point ID	$m,n\le$
$1,2$	$30000$
$3,4$	$50000$
$5,6$	$100000$
$7,8$	$150000$
$9,10$	$200000$

Translated by ChatGPT 5