D. Cross the Storm
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The wulala kingdom is located on the ocean, which consists of $$$n$$$ islands in a line, numbered from $$$1$$$ to $$$n$$$. brz lives in island $$$1$$$.

For every island $$$i\in [1,n)$$$, there is a directed route from $$$i$$$ to $$$i+1$$$ island with length $$$w_i$$$. There is also an air island above the ocean. For every island $$$i\in [1,n]$$$, there is an undirected route between island $$$i$$$ and the air island with length $$$W_i$$$.

On the $$$i$$$-th day, Mandy will be on the island $$$i$$$, and brz is always longing to visit her. However, every day there will be a storm in the kingdom. On the $$$i$$$-th day, the storm will destroy all the directed route $$$(x,x+1)$$$, where $$$x\in [l_i,r_i)$$$, and $$$l_i,r_i$$$ is uniformly chosen among all the possible pair $$$(l,r)$$$ that satisfies $$$1\leq l\leq r\leq i$$$.

For all $$$i\in[1,n]$$$, brz wants to know the expectation of the length of the shortest path from island $$$1$$$ to island $$$i$$$ on the $$$i$$$-th day.

Note that due to the advanced technology that wulala kingdom possesses, the destroyed route will be rebuilt immediately at the end of the $$$i$$$-th day.

Input

The first line contains one integer $$$n~(1\leq n\leq 5\times 10^5)$$$.

The second line contains $$$n-1$$$ integers $$$w_1,w_2\cdots w_{n-1}~(1\leq w_i\leq 10^9)$$$.

The third line contains $$$n$$$ integers $$$W_1,W_2\cdots, W_n~(1\leq W_i\leq 10^9)$$$.

Output

Print $$$n$$$ lines. The $$$i$$$-th line contains the answer of the $$$i$$$-th day module $$$998~244~353$$$.

Examples
Input
2
1
1 1
Output
0
332748119
Input
5
1 2 3 4
5 6 7 8 9
Output
0
332748122
499122184
598946622
665496248