Problem G
Hæg deiling

Inntakið mun gefa þér tvær margliður $P$ og $Q$. Framkvæma má deilingu með afgangi á margliður til að fá $P(x) = Q(x) \cdot D(x) + R(x)$ þar sem stig $R$ er strangt minna en stig $Q$. Þú átt einfaldlega að finna þessar margliður $D, R$.

Inntak

Fyrsta lína inntaksins inniheldur tvær jákvæðar heiltölur $n, m$, fjöldi gefna stuðla í hvorri margliðu. Nánar tiltekið er $P$ með $n$ stuðla og $Q$ með $m$ stuðla. Næstu tvær línur innihalda svo eina margliðu hvor, $P$ á fyrri línu og $Q$ á seinni. Hver margliða er gefin sem stuðlar hennar í vaxandi röð, það er að segja ef inntakið er a0 a1 a2 a3 þá er verið að gefa margliðuna $a_0 + a_1 x + a_2 x^2 + a_3 x^3$. Gefið er að $n, m \leq 1\, 000$ og að allir stuðlar $a_i$ uppfylli $-1\, 000 \leq a_i \leq 1\, 000$. Til að tryggja að úttak hafi heiltölustuðla mun $Q$ alltaf hafa forystustuðul $1$.

Úttak

Prentið margliðurnar $D, R$ eins og lýst er að ofan, á sama formi og margliðurnar í inntakinu. Sleppið öllum auka núllum aftast, það er að segja ef aftasta talan er núll á að sleppa henni nema ef hún er eina talan í úttakinu. Prentið $D$ á fyrri línuna og $R$ á þá seinni. Þar sem stuðlarnir gætu orðið mjög stórir, prentið þá mátaða við $10^9 + 7$. Einnig skal sleppa núllum aftast ef mátun við $10^9 + 7$ er það sem gerir stuðlana að $0$.

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