408066: GYM102978 D Do Use FFT

Memory Limit:1024 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Do Use FFTtime limit per test10 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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) $$$$$$

Input

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$$$).

Output

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

ExampleInput
3
1 2 3
4 5 6
7 8 9
Output
146 1050 8694

加入题单

上一题 下一题 算法标签: