Problem Description

Farmer John’s cows have a strong love for sweets, and they especially enjoy eating candy canes. FJ has $N$ cows, and each cow has a specific initial height. He wants to feed them $M$ candy canes, where each candy cane has its own length ($1 \le N,M \le 2\cdot 10^5$).

FJ plans to feed the cows the candy canes one by one in the order given in the input. Then, the cows will line up in the order given in the input and take turns walking up to the candy cane. Each cow can eat at most the part up to its own height (because it cannot reach any higher). Even if the cows eat away the bottom of the candy cane, the candy cane stays hanging in its original position and will not be lowered to the ground. If the bottom of the candy cane is already higher than a cow’s height, then that cow may eat nothing during its turn. After every cow has taken its turn eating, each cow’s height increases by the number of units of candy cane it ate. Then Farmer John hangs up the next candy cane, and the cows repeat the process (with the first cow again being the first to eat the next candy cane).

Input Format

The first line contains $N$ and $M$.

The next line contains the initial heights of the $N$ cows, where each height is in the range $[1,10^9]$.

The next line contains the lengths of the $M$ candy canes, where each length is in the range $[1,10^9]$.

Output Format

Output $N$ lines, the final height of each cow.

Note that because this problem involves large integers, you may need to use a 64-bit integer type (for example, long long in C/C++).

3 2
3 2 5
6 1

7
2
7

Hint

Sample Explanation 1

The first candy cane has length $6$ units.

• The first cow eats the first candy cane up to height $3$, leaving the remaining part of the first candy cane at heights $[3,6]$.
• The second cow is not tall enough and cannot eat any of the remaining part of the first candy cane.
• The third cow eats an additional $2$ units of the first candy cane. The remaining part of the first candy cane at heights $[5,6]$ is not eaten.

Next, each cow grows by the amount it ate, so the cows’ heights become $[3+3, 2+0, 5+2]=[6, 2, 7]$.

The second candy cane has length $1$ unit and is completely eaten by the first cow.

Test Point Properties

• Test points $2-10$ satisfy $N,M \le 10^3$.
• Test points $11-14$ have no additional constraints.

Translated by ChatGPT 5