Given $F(x) = \displaystyle \sum_{i=0}^{n-1} f_ix^i$ and $G(x) = \displaystyle \sum_{i=0}^{n-1} g_ix^i$, where $g_0 = 0$.

Find the coefficients of $H(x) = F(G(x)) \pmod{x^{n}}$, modulo $998\,244\,353$.

Input

The first line contains an integer $N$.

The next line contains $N$ integers $f_0, f_1, \cdots, f_{n-1}$. It is guaranteed that for each $i$, $0 \leq f_i < 998\,244\,353$.

The next line contains $N$ integers $g_0, g_1, \cdots, g_{n-1}$. It is guaranteed that $g_0 = 0$, and for each $i$, $0 \leq g_i < 998\,244\,353$.

Output

Output one line containing $N$ integers $h_0, h_1, \cdots, h_{n-1}$.

Examples

Input 1

6
1 1 4 5 1 4
0 9 0 2 2 8

Output 1

1 9 324 3647 6707 238778

Subtasks

For all data, we have $1 \leq N \leq 200\,000$.