Modular Polynomial Division

You are given two polynomials \(F(x)\) and \(G(x)\) with degrees \(n\) and \(m\) respectively. It is guaranteed that \(n \ge m\). Your task is to compute two polynomials, the quotient \(Q(x)\) and the remainder \(R(x)\), satisfying

[ F(x) = Q(x) \cdot G(x) + R(x) \quad \text{with} \quad \deg(Q(x)) = n-m \quad \text{and} \quad \deg(R(x)) < m, ]

All operations are performed under modulo \(998244353\). Note that if \(n < m\), you should consider \(Q(x)=0\) and \(R(x)=F(x)\).

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(n \ge m\)).

The second line contains \(n+1\) integers representing the coefficients of \(F(x)\) in descending order (from the coefficient of \(x^n\) to the constant term).

The third line contains \(m+1\) integers representing the coefficients of \(G(x)\) in descending order (from the coefficient of \(x^m\) to the constant term).

outputFormat

Output two lines.

The first line contains \(n-m+1\) integers — the coefficients of the quotient polynomial \(Q(x)\) in descending order.

The second line contains \(m\) integers — the coefficients of the remainder polynomial \(R(x)\) in descending order. (Note: If the remainder is the zero polynomial, output a single 0.)

sample

2 1
1 0 0
1 1

1 998244352
1