문제 98
다항식의 곱
길이가 각각 $N$, $M$인 정수 수열 $a_0, a_1, \cdots, a_{N-1}$과 $b_0, b_1, \cdots, b_{M-1}$이 주어진다. 두 수열을 계수로 하는 다항식 $A(x)$와 $B(x)$를 다음과 같이 정의한다.
$$ A(x)=\sum_{i=0}^{N-1}a_ix^i,\qquad B(x)=\sum_{j=0}^{M-1}b_jx^j. $$
$A(x)B(x)$의 계수를 낮은 차수부터 구해보자.
입력
첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1 \le N, M \le 400\,000)$
두 번째 줄에 $N$개의 정수 $a_0, a_1, \cdots, a_{N-1}$이 공백으로 구분되어 주어진다. $(-10^6 \le a_i \le 10^6)$
세 번째 줄에 $M$개의 정수 $b_0, b_1, \cdots, b_{M-1}$이 공백으로 구분되어 주어진다. $(-10^6 \le b_j \le 10^6)$
출력
$A(x)B(x)$의 계수 $N+M-1$개를 낮은 차수부터 공백으로 구분하여 출력한다.
예제 입력 1
2 3 1 2 3 4 5
예제 출력 1
3 10 13 10
예제 입력 2
3 2 -2 0 3 4 -5
예제 출력 2
-8 10 12 -15