你在玩一个抽卡游戏。

这个游戏有 $n+1$ 种级别的抽卡方式，编号为 $0,1,\cdots,n$ 。抽出来的每张卡的等级是 $[0,m]$ 中的一个整数。

一次 0 级抽卡就是只抽一次卡，而一次 $i$ 级抽卡 $(1\le i\le n)$ 会包含 $b_i$ 次 $i-1$ 级抽卡，并且这次 $i$ 级抽卡合法当且仅当它包含的所有 $i-1$ 级抽卡合法，且抽出来的卡中至少有一张的等级大于等于 $i$ 。

对于每次 0 级抽卡，抽出一张等级为 $j$ 的卡的概率是 $\dfrac{a_j}{\sum_{k=0}^m a_k}$ 。

设 $p_j$ 表示在一次合法的 $n$ 级抽卡中抽出等级为 $j$ 的卡的期望次数，$q$ 表示一次 $n$ 级抽卡合法的概率。你需要对于 $0\le j\le m$ 求出 $(p_j\cdot q)\bmod {998244353}$ 。

输入格式

第一行，两个正整数 $m,n$ 。

第二行， $m+1$ 个正整数 $a_0,a_1,\cdots,a_m$ 。

第三行， $n$ 个正整数 $b_1,b_2,\cdots,b_n$ 。

输出格式

输出 $m+1$ 行，第 $j$ 行一个整数 $(p_{j-1}\cdot q)\bmod {998244353}$ 。

样例一

input

2 1
1 1 1
3

output

554580197
1
1

explanation

共有 $27$ 种 $n$ 级抽卡，每种的可能性相等，且其中 $26$ 种是合法的。

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

样例二

input

3 2
1 1 2 1
2 3

output

58137752
260406016
517809313
758026833

样例三

input

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

output

853156597
693809475
552532484
320522442
504282215
597794834
31931071
464311661

数据范围与提示

本题共 $20$ 组测试点，各 $5$ 分。

对于所有数据，$1\le n\le m\le 4000,1\le a_i\le 4000,2\le b_i\le 4000$ 。保证 $a_i,b_i$ 在范围内均匀随机。

时间限制：$\texttt{5s}$

空间限制：$\texttt{512MB}$