Problem G
Naïve Quotient

The input will give you two polynomials $P$ and $Q$. Division with remainder can be performed on polynomials to get $P(x) = Q(x) \cdot D(x) + R(x)$ where the degree of $R$ is strictly less than the degree of $Q$. You should simply find these polynomials $D, R$.

Input

The first line of input contains two positive integers $n, m$, the number of given coefficients in each polynomial. More specifically, $P$ as $n$ coefficients and $Q$ has $m$ coefficients. The next two lines each contain a polynomial, $P$ on the first line and $Q$ on the second. Each polynomial is given as its coefficient in increasing order. That is to say, if the input is a0 a1 a2 a3 then you are being given the polynomial $a_0 + a_1 x + a_2 x^2 + a_3 x^3$. You may assume that $n, m \leq 1\, 000$ and that all coefficients $a_i$ satisfy $-1\, 000 \leq a_i \leq 1\, 000$. To ensure the output has integer coefficients $Q$ will always be monic, that is, have a leading coefficient $1$.

Output

Print the polynomials $D, R$ as described above, in the same format as the polynomials in the input. Omit any trailing zeroes at the end, that is to say if the last coefficient is zero it should be omitted unless it is the only coefficient. Print $D$ on the first line and $R$ on the second one. As the coefficients may become very large, print them modulo $10^9 + 7$. Trailing zeroes should be omitted even if they are only zero due to the modulo operation.

8 5
12 4 2 7 9 0 0 3
1 0 -7 0 1

9 21 0 3
3 999999990 65 151

6 3
0 39 -50 44 -18 5
3 -2 1

0 13 999999999 5
0