#abc245d. [abc245_d]Polynomial division

[abc245_d]Polynomial division

問題文

NN 次多項式 A(x)=ANxN+AN1xN1+cdots+A1x+A0A(x)=A_Nx^N+A_{N-1}x^{N-1}+\\cdots +A_1x+A_0
MM 次多項式 B(x)=BMxM+BM1xM1+cdots+B1x+B0B(x)=B_Mx^M+B_{M-1}x^{M-1}+\\cdots +B_1x+B_0 があります。
ここで、A(x),B(x)A(x), B(x) の各係数は絶対値が 100100 以下の整数であり、最高次の係数は 00 ではありません。

また、それらの積を $C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\\cdots +C_1x+C_0$ とします。

A0,A1,ldots,ANA_0,A_1,\\ldots, A_N および C0,C1,ldots,CN+MC_0,C_1,\\ldots, C_{N+M} が与えられるので、B0,B1,ldots,BMB_0,B_1,\\ldots, B_M を求めてください。
ただし、与えられる入力に対して、条件をみたす B0,B1,ldots,BMB_0,B_1,\\ldots, B_M がただ一つ存在することが保証されます。

制約

  • 1leqN<1001 \\leq N < 100
  • 1leqM<1001 \\leq M < 100
  • Aileq100|A_i| \\leq 100
  • Cileq106|C_i| \\leq 10^6
  • ANneq0A_N \\neq 0
  • CN+Mneq0C_{N+M} \\neq 0
  • 条件をみたす B0,B1,ldots,BMB_0,B_1,\\ldots, B_M がただ一つ存在する。

入力

入力は以下の形式で標準入力から与えられる。

NN MM A0A_0 A1A_1 ldots\\ldots AN1A_{N-1} ANA_N C0C_0 C1C_1 ldots\\ldots CN+M1C_{N+M-1} CN+MC_{N+M}

出力

M+1M+1 個の整数 B0,B1,ldots,BMB_0,B_1,\\ldots, B_M を空白区切りで一行に出力せよ。


入力例 1

1 2
2 1
12 14 8 2

出力例 1

6 4 2

A(x)=x+2A(x)=x+2, B(x)=2x2+4x+6B(x)=2x^2+4x+6 のとき、C(x)=A(x)B(x)=(x+2)(2x2+4x+6)=2x3+8x2+14x+12C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12 であるので、 B(x)=2x2+4x+6B(x)=2x^2+4x+6 が条件をみたします。 よって、B0=6B_0=6, B1=4B_1=4, B2=2B_2=2 をこの順に空白区切りで出力します。


入力例 2

1 1
100 1
10000 0 -1

出力例 2

100 -1

A(x)=x+100A(x)=x+100, C(x)=x2+10000C(x)=-x^2+10000 であり、B(x)=x+100B(x)=-x+100 が条件をみたします。 よって、100100, \-1\-1 をこの順に空白区切りで出力します。