多项式除法

题目描述

设 $N$ 次多项式 [ A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots+A_1x+A_0, ] 以及 $M$ 次多项式 [ B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots+B_1x+B_0. ] 这里,$A(x)$ 和 $B(x)$ 的各项系数均为绝对值不超过 $100$ 的整数,且首项系数不为 $0$。

另外,设它们的乘积为 [ 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. ]

给定 $A_0,A_1,\ldots,A_N$ 和 $C_0,C_1,\ldots,C_{N+M}$,求 $B_0,B_1,\ldots,B_M$。

这里,题目保证满足给定条件的序列 $B_0,B_1,\ldots,B_M$ 唯一。

输入格式

输入按以下格式从标准输入给出:

N M
A_0 A_1 … A_{N-1} A_N
C_0 C_1 … C_{N+M-1} C_{N+M}

输出格式

在一行中输出 $M+1$ 个整数 $B_0,B_1,\ldots,B_M$,用空格隔开。

样例

1 2
2 1
12 14 8 2

6 4 2

对 $A(x)=x+2$、$B(x)=2x^2+4x+6$,有 [ C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12, ] 所以 $B(x)=2x^2+4x+6$ 满足条件。因此按顺序输出 $B_0=6$、$B_1=4$、$B_2=2$,用空格隔开。

1 1
100 1
10000 0 -1

100 -1

有 $A(x)=x+100$,$C(x)=-x^2+10000$,此时 $B(x)=-x+100$ 满足条件。因此按顺序输出 $100$、$-1$,用空格隔开。

数据范围

• $1 \le N \lt 100$
• $1 \le M \lt 100$
• $|A_i| \le 100$
• $|C_i| \le 10^6$
• $A_N \neq 0$
• $C_{N+M} \neq 0$
• 满足题述条件的序列 $B_0,B_1,\ldots,B_M$ 唯一存在。