No submission language available for this problem.

Description

Input

The first line contains an integer $n$ ($1\le n\le 700$).

The second line contains $n$ integers $a_1,\ldots,a_n$ ($0\le a_i<998\,244\,353$).

The third line contains $n$ integers $b_1,\ldots,b_n$ ($0\le b_i<998\,244\,353$).

The fourth line contains $n$ integers $c_0,\ldots,c_{n-1}$ ($0\le c_i<998\,244\,353$).

Output

Print $n$ integers: the $i$-th one is $f(i)$ modulo $998\,244\,353$.

3
1 1 1
1 1 1
1 1 1

1 2 6

3
1 2 3
2 3 1
3 1 2

6 13 34

5
1 4 2 5 3
2 5 1 3 4
300000000 100000000 500000000 400000000 200000000

600000000 303511294 612289529 324650937 947905622

Note

In the second example:

• Consider permutation $[1,2,3]$. Indices $1,2,3$ are prefix maximums. Index $3$ is the only suffix maximum. Indices $2,3$ are ascents. In conclusion, it has $3$ prefix maximums, $1$ suffix maximums, and $2$ ascents. Therefore, its cost is $a_3b_1c_2=12$.
• Permutation $[1,3,2]$ has $2$ prefix maximums, $2$ suffix maximums, and $1$ ascent. Its cost is $6$.
• Permutation $[2,1,3]$ has $2$ prefix maximums, $1$ suffix maximum, and $1$ ascent. Its cost is $4$.
• Permutation $[2,3,1]$ has $2$ prefix maximums, $2$ suffix maximums, and $1$ ascent. Its cost is $6$.
• Permutation $[3,1,2]$ has $1$ prefix maximum, $2$ suffix maximums, and $1$ ascent. Its cost is $3$.
• Permutation $[3,2,1]$ has $1$ prefix maximum, $3$ suffix maximums, and $0$ ascents. Its cost is $3$.

The sum of all permutations' costs is $34$, so $f(3)=34$.