装箱土豆

题目描述

有 $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$ 个箱子会被密封。

输入格式

输入按以下格式从标准输入给出:

N Q X
W_0 W_1 … W_{N-1}
K_1
⋮
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

数据范围

• $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)$
• 输入中的所有值均为整数。