题目描述

游戏策划奈央正在设计一套阶梯抽卡系统。游戏中有 $0$ 星、$1$ 星、$\ldots$、$m$ 星物品。一次单抽抽到 $i$ 星物品的概率为

一次单抽称为 $0$ 级抽取。对于 $k\ge 1$，一次 $k$ 级抽取由恰好 $b_k$ 轮 $(k-1)$ 级抽取组成。最高级别为 $n$。

一次 $k$ 级抽取是合法的，当且仅当它保证以下条件：

• 至少抽到一个星级不低于 $k$ 的物品；
• 它包含的所有 $b_k$ 次 $(k-1)$ 级抽取中，每一次都至少抽到一个星级不低于 $k-1$ 的物品；
• 递归地，直到 $0$ 级抽取；对于一次单抽而言，至少抽到一个星级不低于 $0$ 的物品显然恒成立。

令 $p_i$ 表示在一次合法的 $n$ 级抽取中，抽到 $i$ 星物品数量的期望；令 $q$ 表示一次 $n$ 级抽取合法的概率。

你需要对所有 $0\le i\le m$，输出

这样可以避免直接处理巨大分数和除零问题。

输入格式

第一行包含两个整数 $m,n$，分别表示最高星级和最高抽取级别。

第二行包含 $m+1$ 个整数

表示抽到各星级物品的频数。

第三行包含 $n$ 个整数

表示 $1,2,\ldots,n$ 级抽取分别包含多少次上一级抽取。

输出格式

输出 $m+1$ 行。第 $i$ 行输出一个整数，表示

数据范围

• $1\le n\le m\le 4000$；
• $1\le a_i\le 4000$；
• $2\le b_i\le 4000$。

样例 1

输入

2 1
1 1 1
3

输出

554580197
1
1

解释

样例 1 的答案写成有理数形式分别为：

样例 2

输入

2 1
89 10 1
10

输出

989586456
1
299473306

样例 3

输入

3 2
1 1 2 1
2 3

输出

58137752
260406016
517809313
758026833