[ABC359] E - Water Tank

E - Water Tank

Time Limit: 2 sec / Memory Limit: 1024 MB

分数：500分

故事

有一个长水槽，水槽上放着不同高度的木板，木板间距相等。高桥想要知道从水槽的一端倒水时，水什么时候到达每块木板之间的部分。

题面

给定长度为的正整数序列：。

有一个长度为的非负整数序列：。初始时，。

在上重复执行以下操作：

1. 将的值增加。
2. 对于按顺序执行以下操作：
   • 如果且，则将的值减少，将的值增加。

对于每个，找到在第一次成立之前的操作次数。

限制条件

• 所有输入值均为整数。

---

输入

从标准输入读入数据，格式如下：

输出

在一行中输出对应的答案，用空格分隔。

---

示例输入 1

5
3 1 4 1 5

示例输出 1

4 5 13 14 26

前五步操作如下所示。

在该图中，每一行对应一次操作，最左侧列表示第1步，其他列表示第2步。

从这个图表可以看出，在第4次操作后首次成立，在第5次操作后首次成立。

类似地，的答案分别是。

因此，应输出4 5 13 14 26。

---

示例输入 2

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

示例输出 2

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

请注意，要输出的值可能超出32位整数的范围。

---

示例输入 3

15
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632

示例输出 3

749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373