시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 1024 MB 2 2 2 100.000%

문제

You are given integer sequences $A$, $B$, and $C$, each of length $N$. For each $k=1,2,\ldots,N$, find the following value modulo $998244353$.

$$ \sum_{1 \leq i \leq N} \left( C_i \times \prod_{1 \leq j \leq k} (A_i+B_j) \right) $$

입력

The first line contains an integer $N$ ($1 \leq N \leq 250000$).

The second line contains $N$ integers $A_1,A_2,\ldots,A_N$ ($0 \leq A_i < 998244353$).

The third line contains $N$ integers $B_1,B_2,\ldots,B_N$ ($0 \leq B_i < 998244353$).

The fourth line contains $N$ integers $C_1,C_2,\ldots,C_N$ ($0 \leq C_i < 998244353$).

출력

For each $k=1,2,\ldots,N$, print the answer.

예제 입력 1

3
1 2 3
4 5 6
7 8 9

예제 출력 1

146 1050 8694