Gachapon

According to Wikipedia, "a gacha game is a video game that implements the gacha (toy vending machine) mechanic". Similar to loot boxes, gacha games lead players to spend in-game currency to receive a random virtual item.

One such game is Step-up Gacha, where the chance of rolling a rare item rises each time the player rolls. For example, Genshin Impact guarantees that a player can always draw a four-star item or character within any ten consecutive rolls.

Abstracting these rolling rules helps. Consider a game with $0$-star, $1$-star, $\ldots$, $m$-star items. The probability of drawing an $i$-star item in a single roll is $\frac{a_i}{\sum_{j=0}^{m} a_j}$. A single draw is a level $0$ rolling, and a level $k$ rolling consists of exactly $b_k$ rounds of level $(k-1)$ rollings. The highest level of a rolling is $n$.

A level $k$ rolling is legal if it ensures the following:

• at least one item with at least $k$ stars is drawn,
• for all $b_k$ level $(k-1)$ rollings it contains, at least one item with at least $(k-1)$ stars is drawn,
• and so on, down to each level $0$ rolling (a single draw), for which at least one item with at least $0$ stars is drawn trivially.

Let $p_i$ be the expected number of $i$-star items drawn from a legal $n$-level rolling, and let $q$ be the probability that an $n$-level rolling is legal. Find the values of $p_i$ and $q$. To avoid huge numbers and divisions by zero, for every $0 \le i \le m$, output only the value $(p_i \cdot q) \bmod 998\,244\,353$.

The first line contains two integers $m$ and $n$: the maximum number of stars and the highest level of a rolling ($1 \le n \le m \le 4000$).

The second line contains $m + 1$ integers $a_0, a_1, \ldots, a_m$: the frequencies of rolling items with $0, 1, \ldots, m$ stars ($1 \le a_i \le 4000$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$: the number of previous level rollings in a rolling of level $1, 2, \ldots, n$ ($2 \le b_i \le 4000$).

Output $m+1$ lines. The $i$-th line should contain a single integer: the value of $(p_{i-1} \cdot q) \bmod 998\,244\,353$.

In the first example, the answers in rational form are: $\frac{8}{9}$, $1$, $1$.