题目描述

sstzer 养了一群很不老实的马，它们尤其喜欢跳到 sstzer 家门口的竹子上。sstzer 共有 $N$ 只马，每只马都有一个初始跳跃高度。sstzer家门口种了一排竹子，共有 $M$ 颗。每颗竹子的高度也各不相同（$1 \le N,M \le 2\cdot 10^5$）。

sstzer家门口的竹子按输入顺序排成一排。然后，sstzer的马会按照输入给出的顺序一个接一个地排队尝试跳上这些竹子，但不幸的是，马在尝试跳上竹子的时候会破坏掉当前竹子从地面到它当前跳跃高度的部分。出于minecraft的某种神奇特性，剩余的竹子将会悬浮在空中。如果竹子的底部已经高于某匹马的跳跃高度，那么这只马在它的回合中什么也破坏不了。如果马的跳跃高度高于竹子的高度，那么这根竹子的所有剩余部分将被破坏。每匹马轮流尝试过后，它们的跳跃高度会增加它们破坏的竹子的格数，然后它们会开始尝试跳上下一个竹子，这群马会再次重复这个过程（第一个尝试跳跃的还是第一匹马）。

输入格式

从文件 $horse.in$ 中读入数据

第一行包含 $N$ 和 $M$。

接下来的一行包含 $N$ 只马的初始跳跃高度，每匹马的跳跃高度都在 $[1,10^9]$ 的范围内。

接下来的一行包含 $M$ 颗竹子的高度，每颗竹子的高度都在 $[1,10^9]$ 的范围内。

输出格式

输出数据到文件 $horse.out$

输出 $N$ 行，表示每只马最终的跳跃高度。

请注意，由于这个问题涉及的整数大小较大，可能需要使用 64 位整数数据类型（例如，在 C/C++ 中使用 long long 类型）。

样例

3 2
3 2 5
6 1

7
2
7

提示

样例解释 1

第一颗竹子高度为 $6$ 格。

• 第一匹马破坏掉了第一颗竹子直至高度 $3$ 的部分，之后第一颗竹子剩余高度 $[3,6]$ 的部分。
• 第二匹马跳的不够高，无法破坏第一颗竹子的任何剩余部分。
• 第三匹马额外破坏掉了第一颗竹子的两格。第一颗竹子的剩余高度 $[5,6]$ 的部分未被破坏。

接下来，每匹马根据它破坏掉的数量增长跳跃高度，所以马的跳跃高度变为 $[3+3, 2+0, 5+2]=[6, 2, 7]$。

第二颗竹子高度为 $1$ 单位，被第一匹马全部破坏。

测试点性质

• 测试点 $2-10$ 满足 $N,M \le 10^3$。
• 测试点 $11-14$ 没有额外限制。