다항식의 나눗셈

다항식 $f(x) = \sum _ {i = 0} ^ {N - 1} f _ i x^i \in \mathbb{F} _ {998244353}[x]$와 $g(x)=\sum _ {i=0}^{M-1}g_ix^i\in \mathbb{F}_{998244353}[x]$가 주어진다. 다음을 만족하는 다항식 $q(x)$와 $r(x)$를 계산한다.

• $f(x) = q(x)g(x) + r(x)$이고
• $\deg(r) \lt \deg(g)$이다.

제약 조건

• $1 \leq N \leq 500000$
• $1 \leq M \leq 500000$
• $0 \leq f_i < 998244353$
• $0 \leq g_i < 998244353$
• $f_{N-1} \neq 0$
• $g_{M-1} \neq 0$

$N\ M$
$f_0\ f_1\ \ldots\ f_{N - 1}$
$g_0\ g_1\ \ldots\ g_{M - 1}$

첫째 줄에 $u=\deg(q)+1$와 $v=\deg(r)+1$를 출력한다. $q(x) = 0$이면 대신 $u = 0$로 둔다. ($r(x)$도 마찬가지이다.)

둘째 줄에 $q(x)$의 계수를 출력하고, 셋째 줄에 $r(x)$의 계수를 출력한다.

$u\ v$
$q_0\ q_1\ \ldots\ q_{u-1}$
$r_0\ r_1\ \ldots\ r_{v-1}$