Problem11322--[yosupo] Polynomial - Inv of Polynomials

11322: [yosupo] Polynomial - Inv of Polynomials

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

We consider polynomials over $\mathbb{F}_{998244353}$ in this problem.

Given polynomials $f(x)=\sum_{i=0}^{N-1} a_ix^i$ and $g(x)=\sum_{i=0}^{M-1}b_ix^i$.
Calculate a polynomial $h(x)=\sum_{i=0}^{T-1}c_ix^i$ s.t.

- $\deg(h) < \deg(g)$ and
- $f(x)h(x)\equiv1\pmod {g(x)}$


is satisfied.

We note that $\deg(0)=-\infty$ in this problem.
We can prove $h(x)$ is unique if it exists.
Print $-1$ if it doesn't exist.

Input

$N$ $M$
$a_0$ $a_1$ $\ldots$ $a_{N - 1}$
$b_0$ $b_1$ $\ldots$ $b_{M - 1}$

Output

If $h(x)$ doesn't exist, print $-1$.

If $h(x)$ exists, print $T$ ($c_{T-1} \neq 0$) in first line, or $T = 0$ when $h(x)=0$.
Print $c_0, c_1, \ldots, c_{T-1}$ in next line.


$T$
$c_0$ $c_1$ $\ldots$ $c_{T - 1}$

Constraints

- $1 \leq N \leq 50000$
- $1 \leq M \leq 50000$
- $0 \leq a_i < 998244353$
- $0 \leq b_i < 998244353$
- $a_{N-1} \neq 0$
- $b_{M-1} \neq 0$

Sample 1 Input

5 5
5 4 3 2 1
1 2 3 4 5

Sample 1 Output

2
598946612 831870294

Sample 2 Input

5 1
5 4 3 2 1
7

Sample 2 Output

0

Sample 3 Input

3 3
2 3 1
6 5 1

Sample 3 Output

-1

HINT

Source/Category