分数: 500 点
问题陈述
10^{100} 土豆从传送带上一颗一颗地送来。土豆的重量由序列描述 W = (W_0, \dots, W_{N-1}) 长度 N:重量 i-第一个土豆来了 W_{(i-1) \bmod N},其中 (i-1) \bmod N 表示当 i - 1 除以 N.
高桥会准备一个空盒子,然后按顺序包装土豆,如下。
- 将收到的土豆装入盒子中。如果现在盒子里土豆的总重量是 X 或更大,密封该盒子并准备一个新的空盒子。
你被给予 Q 查询。在 i第一个查询 (1 \leq i \leq Q),给定一个正整数 K_i,找出土豆的数量 K_i第一个盒子要密封。可以证明,在问题的约束下,至少会有 K_i 密封盒。
约束
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq X \leq 10^9
- 1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)
- 1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q X
W_0 W_1 \ldots W_{N-1}
K_1
\vdots
K_Q
输出
打印 Q 行。的 i第行 (1 \leq i \leq Q) 应包含以下问题的答案 i第一个查询。
示例输入 1
3 2 5 3 4 1 1 2
示例输出 1
2 3
密封之前 2-nd 框中,高桥将执行以下操作:
- 准备一个空盒子。
- 打包 1-st土豆入盒。现在,盒子里土豆的总重量是 3.
- 打包 2-将土豆放入盒子中。现在,盒子里土豆的总重量是 3 + 4 = 7,不小于 X = 5,所以密封这个盒子。
- 准备一个新的空盒子。
- 打包 3-rd土豆放入盒子中。现在,盒子里土豆的总重量是 1.
- 打包 4第一个土豆放入盒子中。现在,盒子里土豆的总重量是 1 + 3 = 4.
- 打包 5第一个土豆放入盒子中。现在,盒子里土豆的总重量是 1 + 3 + 4 = 8,不小于 X = 5,所以密封这个盒子。
的 1-st 密封盒包含 2 土豆,以及 2-nd 盒子密封包含 3 土豆。
示例输入 2
10 5 20 5 8 5 9 8 7 4 4 8 2 1 1000 1000000 1000000000 1000000000000
示例输出 2
4 5 5 5 5