根据维基百科，“扭蛋游戏（gacha game）是一种实现了扭蛋（玩具自动售货机）机制的电子游戏”。与战利品箱类似，扭蛋游戏诱导玩家花费游戏内货币来获取随机的虚拟物品。

其中一种扭蛋游戏被称为“保底扭蛋（Step-up Gacha）”，这意味着玩家每次抽卡时，获得稀有物品的概率都会增加。例如，热门游戏《原神》确保你在任意十连抽中都能获得四星物品或角色。

如果我们能为这些抽卡规则提供一个抽象模型将会很有帮助。考虑一个包含 0 星、1 星、……、$m$ 星物品的游戏。假设单次抽卡抽到 $i$ 星物品的概率为 $\frac{a_i}{\sum_{j=0}^m a_j}$。单次抽取即为 0 级抽卡，而 $k$ 级抽卡由 $b_k$ 轮 $(k-1)$ 级抽卡组成。抽卡的最高等级为 $n$。

如果 $k$ 级抽卡满足以下条件，则称其为合法的： 至少抽到一个星级不低于 $k$ 的物品， 对于它包含的所有 $b_k$ 轮 $(k-1)$ 级抽卡，每一轮都至少抽到一个星级不低于 $(k-1)$ 的物品， * ……以此类推，直到每一轮 0 级抽卡（即单次抽取），每一轮都平凡地满足至少抽到一个星级不低于 0 的物品。

设 $p_i$ 为从一次合法的 $n$ 级抽卡中抽出的 $i$ 星物品的期望数量，设 $q$ 为一次 $n$ 级抽卡合法的概率。求 $p_i$ 和 $q$ 的值。为了避免出现巨大的数字和除以零的情况，对于所有 $0 \le i \le m$，你只需要输出 $(p_i \cdot q) \pmod{998\,244\,353}$ 的值。

输入格式

第一行包含两个整数 $m$ 和 $n$：最大星级数和抽卡的最高等级（$1 \le n \le m \le 4000$）。

第二行包含 $m+1$ 个整数 $a_0, a_1, \dots, a_m$：抽到 $0, 1, \dots, m$ 星物品的频率（$1 \le a_i \le 4000$）。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$：等级 $1, 2, \dots, n$ 的抽卡中包含的上一级抽卡轮数（$2 \le b_i \le 4000$）。

输出格式

输出 $m+1$ 行。第 $i$ 行应包含一个整数：$(p_{i-1} \cdot q) \pmod{998\,244\,353}$ 的值。

样例

样例输入 1

2 1
1 1 1
3

样例输出 1

554580197
1
1

样例输入 2

2 1
89 10 1
10

样例输出 2

989586456
1
299473306

样例输入 3

3 2
1 1 2 1
2 3

样例输出 3

58137752
260406016
517809313
758026833

说明

在第一个样例中，答案的有理数形式为：$\frac{8}{9}, 1, 1$。