Given an $n$-th degree polynomial $A(z)=\sum^n_{i=0} a_iz^i$ and an $m$-th degree polynomial $B(z)=\sum^m_{i=0} b_iz^i$, find their product $C(z) = \sum^{n+m}_{i=0} c_iz^i$, modulo 998244353.

Input

The first line contains two integers $n, m$.

The next line contains $n + 1$ integers $a_0, a_1, \dots, a_n$.

The next line contains $m + 1$ integers $b_0, b_1, \dots, b_m$.

Output

Output a single line containing $n+m+1$ integers, representing $c_0, c_1, \dots, c_{n+m}$.

Examples

Input 1

2 3
1 2 3
3 4 5 6

Output 1

3 10 22 28 27 18

Subtasks

For all data, $1 \leq n, m \leq 10^6$, $0 \le a_i, b_i < 998\,244\,353$.