USACO 2023 December Contest, Bronze

Problem 1. Candy Cane Feast

一、题目描述

农夫约翰的奶牛们非常喜欢甜食，尤其喜欢吃糖果棒！农夫约翰总共有(N)头奶牛，每头奶牛都有特定的初始高度，并且他想给它们喂(M)个糖果棒，每个糖果棒的高度也各不相同$(1\leq N,M\leq2\cdot10^5)$。

农夫约翰计划按照输入的顺序逐个给奶牛喂糖果棒。为了给奶牛喂糖果棒，他会把糖果棒挂起来，使得最初糖果棒刚好接触地面。然后奶牛们会按照输入的顺序一个接一个地排队，走到糖果棒前，每头奶牛最多吃到与自身高度相等的部分（因为它们够不到更高的地方）。即使奶牛吃掉了糖果棒底部部分，糖果棒仍保持在最初设置的位置，不会被降低到地面。如果糖果棒底部已经高于某头奶牛的高度，那么这头奶牛在轮到它时可能什么都吃不到。每头奶牛轮完后，它们的高度会增加吃掉的糖果棒单位数量，然后农夫约翰挂上下一个糖果棒，奶牛们再次重复这个过程（奶牛 1 再次首先开始吃下一个糖果棒）。

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

1. 第一行包含(N)和(M)。
2. 下一行包含(N)头奶牛的初始高度，每个高度在([1,10^9])范围内。
3. 再下一行包含(M)个糖果棒的高度，每个高度在([1,10^9])范围内。

三、输出格式（输出到终端/标准输出）

每行输出(N)头奶牛的最终高度。

注意，此问题中涉及的大整数可能需要使用 64 位整数数据类型（例如，C/C++中的“long long”）。

四、样例输入

   3 2
   3 2 5
   6 1

五、样例输出

   7
   2
   7

六、样例解释

第一个糖果棒高(6)个单位。

1. 第一头奶牛吃掉第一个糖果棒高度为(3)的部分，之后第一个糖果棒剩余部分占据高度([3,6])。
2. 第二头奶牛不够高，无法吃到第一个糖果棒剩余部分。
3. 第三头奶牛吃掉第一个糖果棒额外的(2)个单位。第一个糖果棒剩余部分（占据高度([5,6])）未被吃掉。

接着，每头奶牛根据吃掉的量增加高度，所以奶牛的高度变为([3 + 3,2 + 0,5 + 2]=[6,2,7])。

第二个糖果棒高(1)个单位，第一头奶牛吃掉了它。

七、评分

1. 输入 2 - 10：$N,M\leq10^3$。
2. 输入 11 - 14：无其他额外限制。