Farmer John's Cows and Candy Canes

问题描述

Farmer John 的奶牛非常喜欢吃糖果棒！FJ 总共有 N 头奶牛，每头奶牛都有一定的初始高度，他想要喂 M 根不同高度的糖果棒（1 ≤ N, M ≤ $2·10^5$）。

FJ 计划按照输入顺序逐一喂食糖果棒。为了喂食一根糖果棒，他会把糖果棒悬挂起来，使糖果棒刚好触地。奶牛们会按照输入顺序排队，依次走到糖果棒前，每头奶牛可以吃到与自己身高相等的高度（因为她们无法够到更高的地方）。即使奶牛在她的回合中可能什么都吃不到，如果糖果棒底部已经高于那头奶牛的高度，糖果棒也会保持原位悬挂在最初设置的位置。每次所有奶牛都吃过之后，奶牛们的身高会根据她们吃了多少单位的糖果棒而增长，然后 FJ 会挂起下一根糖果棒，奶牛们重复这个过程（第一头奶牛再次开始吃下一根糖果棒）。

输入格式（从终端/标准输入读入）

• 第一行包含两个整数 N 和 M。
• 第二行包含 N 个整数，表示 N 头奶牛的初始高度，每个高度范围在 [1, $10^9$]。
• 第三行包含 M 个整数，表示 M 根糖果棒的高度，每个高度范围在 [1, $10^9$]。

输出格式（输出至终端/标准输出）

• 输出 N 行，每行一个整数，表示每头奶牛最终的高度。
• 注意：由于本问题涉及的大整数可能需要使用64位整数数据类型（例如C/C++中的"long long"）。

样例输入

3 2
3 2 5
6 1

7
2
7

样例解释

• 第一根糖果棒有 6 单位高。
  • 第一头奶牛吃到高度 3 的部分，剩下的糖果棒占据高度 [3, 6]。
  • 第二头奶牛不够高，吃不到剩余的糖果棒。
  • 第三头奶牛再吃掉两单位的糖果棒。剩下的糖果棒占据高度 [5, 6]，未被吃掉。
• 每头奶牛按各自吃掉的糖果棒量增长，奶牛的高度变为 [3+3, 2+0, 5+2] = [6, 2, 7]。
• 第二根糖果棒只有 1 单位高，第一头奶牛吃掉了全部。

评分标准

• 测试点 2-10: N, M ≤ $10^3$
• 测试点 11-14: 没有额外限制。
• 问题提供者: Agastya Goel

来源

一本通在线评测