19019번 - Convolution 다국어

문제

You are given two sequences $a_0, a_1, \ldots, a_n$ and $b_0, b_1, \ldots, b_n$. You want to compute a new sequence $c_0, c_1, \ldots, c_n$ such that $$c_k = \left(\sum_{i = 0}^k {k \choose i} a_i b_{k-i}\right) \bmod 2^{32}\text{.}$$

Here, ${k \choose i} = \frac{k!}{i! (k - i)!}$ are binomial coefficients.

Output $c_0, c_1, \ldots, c_n$.

입력

The first line contains an integer $n$ (1ドル \leq n \leq 2 \cdot 10^5$).

The second line contains $n + 1$ integers $a_0, a_1, \ldots, a_n$ (0ドル\leq a_i < 2^{32}$).

The third line contains $n + 1$ integers $b_0, b_1, \ldots, b_n$ (0ドル \leq b_i < 2^{32}$).

출력

Output one line with $n + 1$ integers: $c_0, c_1, \ldots, c_n$.

제한

힌트