You are playing a card-drawing game.

This game has $n+1$ levels of card-drawing methods, numbered $0, 1, \dots, n$. The level of each card drawn is an integer in $[0, m]$.

A level 0 draw consists of drawing a single card. A level $i$ draw ($1 \le i \le n$) consists of $b_i$ level $i-1$ draws. A level $i$ draw is valid if and only if all the level $i-1$ draws it contains are valid, and at least one of the cards drawn has a level greater than or equal to $i$.

For each level 0 draw, the probability of drawing a card of level $j$ is $\dfrac{a_j}{\sum_{k=0}^m a_k}$.

Let $p_j$ be the expected number of times a card of level $j$ is drawn in a valid level $n$ draw, and let $q$ be the probability that a level $n$ draw is valid. You need to calculate $(p_j \cdot q) \bmod {998244353}$ for all $0 \le j \le m$.

Input

The first line contains two positive integers $m, n$.

The second line contains $m+1$ positive integers $a_0, a_1, \dots, a_m$.

The third line contains $n$ positive integers $b_1, b_2, \dots, b_n$.

Output

Output $m+1$ lines, where the $j$-th line contains the integer $(p_{j-1} \cdot q) \bmod {998244353}$.

Examples

Input 1

2 1
1 1 1
3

Output 1

554580197
1
1

Note 1

There are $27$ possible level $n$ draws, each equally likely, and $26$ of them are valid.

$\frac 8 9 = 554580197 \pmod{998244353}$

Input 2

3 2
1 1 2 1
2 3

Output 2

58137752
260406016
517809313
758026833

Input 3

7 5
1 2 3 4 5 6 7 8
2 3 4 5 6

Output 3

853156597
693809475
552532484
320522442
504282215
597794834
31931071
464311661

Constraints

There are 20 test cases in total, each worth 5 points.

For all data, $1 \le n \le m \le 4000, 1 \le a_i \le 4000, 2 \le b_i \le 4000$. It is guaranteed that $a_i, b_i$ are uniformly random within the range.