当前没有测试数据。

E - 装土豆

得分：500点

问题描述

有 $10^{100}$ 个土豆从一个传送带上一次传送一个。土豆的重量由长度为 $N$ 的序列 $W = (W_0, \dots, W_{N-1})$ 描述：第 $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$ 个查询的答案。

3 2 5
3 4 1
1
2

2
3

在封上第 $2$ 个盒子之前，高桥将按以下步骤操作：

• 准备一个空盒子。
• 将第 $1$ 个土豆装进盒子中。此时，盒子中土豆的总重量为 $3$。
• 将第 $2$ 个土豆装进盒子中。此时，盒子中土豆的总重量为 $3 + 4 = 7$，大于等于 $X = 5$，所以封上这个盒子。
• 准备一个新的空盒子。
• 将第 $3$ 个土豆装进盒子中。此时，盒子中土豆的总重量为 $1$。
• 将第 $4$ 个土豆装进盒子中。此时，盒子中土豆的总重量为 $1 + 3 = 4$。
• 将第 $5$ 个土豆装进盒子中。此时，盒子中土豆的总重量为 $1 + 3 + 4 = 8$，大于等于 $X = 5$，所以封上这个盒子。

第 $1$ 个封好的盒子中有 $2$ 个土豆，第 $2$ 个封好的盒子中有 $3$ 个土豆。

10 5 20
5 8 5 9 8 7 4 4 8 2
1
1000
1000000
1000000000
1000000000000

4
5
5
5
5