Dok 正在玩一款名为《寿司英雄》（“Hero of Sushi”）的游戏。游戏的规则对我们来说并不重要；只需要知道它由编号从 $1$ 到 $n$ 的回合组成。
Dok 控制着英雄；英雄在游戏中有一个货币余额，初始时为 $0$ 图格里克（tugriks）。在完成第 $i$ 个回合后，他的余额中会增加 $a_i$ 图格里克。
此外，在完成每个回合后，英雄可以进入游戏内的寿司商店。该商店的内容和意义对我们来说并不重要；只需要知道它可以被重刷（reroll）。
每次光顾寿司商店时，第一次重刷花费 $c_1$ 图格里克，第二次花费 $c_2$ 图格里克，依此类推。此外，$1 \le c_1 \le c_2 \le \dots \le c_m$。在任何一次光顾商店期间，英雄可以进行 $0$ 到 $m$ 次之间的任意次数的重刷，但在任何时间点，他的余额都不能少于 $0$ 图格里克。
在游戏中也可以跳过某些回合。如果你跳过了第 $i$ 个回合，你将不会获得该回合的 $a_i$ 图格里克，也无法进入商店。
Dok 非常想知道，如果他跳过前 $t$ 个回合，他的英雄在所有商店中总共最多可以进行多少次重刷，对于每个从 $0$ 到 $n - 1$ 的 $t$。不幸的是，他不是一名程序员，所以他向你寻求帮助。
输入格式
输入数据的第一行包含两个整数 $n, m$ ($1 \le n, m \le 3 \cdot 10^5$) —— 游戏中的回合数以及在一家商店中最多可以进行的重刷次数。
第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^{12}$) —— 完成每个回合所获得的金钱数量。
第三行包含 $m$ 个整数 $c_1, \dots, c_m$ ($1 \le c_i \le 10^{12}$，$c_1 \le c_2 \le \dots \le c_m$) —— 其中 $c_i$ 是每次光顾商店时第 $i$ 次重刷的价格。
输出格式
输出 $n$ 个整数 —— 如果跳过前 $t$ 个回合，在所有商店中总共最多可以进行的重刷次数，对于每个从 $0$ 到 $n - 1$ 的 $t$。
样例
输入样例 1
5 4 6 2 12 6 3 1 3 3 5
输出样例 1
13 10 9 4 1
说明
在第一个样例中，如果 Dok 不跳过任何回合，他将能够按照以下方案在所有商店中总共进行 $13$ 次重刷：
- 在第一回合后，进行 $2$ 次重刷，花费 $1 + 3 = 4$ 图格里克，余额剩余 $2$ 图格里克。
- 在第二回合后，再进行 $2$ 次重刷，花费 $1 + 3 = 4$ 图格里克，余额剩余 $0$ 图格里克。
- 在第三回合后，再进行 $3$ 次重刷，花费 $1 + 3 + 3 = 7$ 图格里克，余额剩余 $5$ 图格里克。
- 在第四回合后，再进行 $3$ 次重刷，花费 $1 + 3 + 3 = 7$ 图格里克，余额剩余 $4$ 图格里克。
- 在第五回合后，再进行 $3$ 次重刷，花费 $1 + 3 + 3 = 7$ 图格里克，余额剩余 $0$ 图格里克。