#2077. [USACO23DEC] Candy Cane Feast B

[USACO23DEC] Candy Cane Feast B

题目描述

Farmer John 的奶牛对甜食情有独钟,它们尤其喜欢吃糖果棒。FJ 共有 NN 头奶牛,每头奶牛都有一个特定的初始高度。他想要喂它们 MM 根糖果棒,每根糖果棒的高度也各不相同(1N,M21051 \le N,M \le 2\cdot 10^5)。

FJ 计划按照输入给出的顺序,逐一喂给奶牛们糖果棒。然后,奶牛们会按照输入给出的顺序一个接一个地排队,走向糖果棒,每头奶牛最多吃到与它高度相同的部分(因为它们够不到更高的地方)。即使奶牛吃掉了糖果棒的底部,糖果棒也在最初悬挂的地方保持不动,并不会被降低到地面。如果糖果棒的底部已经高于某头奶牛的高度,那么这头奶牛在它的回合中可能什么也吃不到。每头奶牛轮流吃过后,它们的身高会增加它们吃掉的糖果棒的单位数量,然后农夫约翰挂上下一根糖果棒,奶牛们再次重复这个过程(第一头奶牛再次成为第一个开始吃下一根糖果棒的)。

输入格式

第一行包含 NNMM

接下来的一行包含 NN 头奶牛的初始高度,每头奶牛的高度都在 [1,109][1,10^9] 的范围内。

接下来的一行包含 MM 根糖果棒的长度,每根糖果棒的长度都在 [1,109][1,10^9] 的范围内。

输出格式

输出 NN 行,表示每头奶牛最终的高度。

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

样例 #1

样例输入 #1

3 2
3 2 5
6 1

样例输出 #1

7
2
7

提示

样例解释 1

第一根糖果棒高度为 66 单位。

  • 第一头奶牛吃掉了第一根糖果棒直至高度 33 的部分,之后第一根糖果棒剩余高度 [3,6][3,6] 的部分。
  • 第二头奶牛不够高,无法吃掉第一根糖果棒的任何剩余部分。
  • 第三头奶牛额外吃掉了第一根糖果棒的两个单位。第一根糖果棒的剩余高度 [5,6][5,6] 的部分未被吃掉。

接下来,每头奶牛根据它吃掉的数量增长,所以奶牛的高度变为 [3+3,2+0,5+2]=[6,2,7][3+3, 2+0, 5+2]=[6, 2, 7]

第二根糖果棒高度为 11 单位,被第一头奶牛全部吃掉。

测试点性质

  • 测试点 2102-10 满足 N,M103N,M \le 10^3
  • 测试点 111411-14 没有额外限制。