Score : $500$ points

问题描述

$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$ 个被封住的箱子。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

$10^{100}$ potatoes are coming from a conveyor belt one by one. The weights of the potatoes are described by a sequence $W = (W_0, \dots, W_{N-1})$ of length $N$: the weight of the $i$-th potato coming is $W_{(i-1) \bmod N}$, where $(i-1) \bmod N$ denotes the remainder when $i - 1$ is divided by $N$.

Takahashi will prepare an empty box and then pack the potatoes in order, as follows.

• Pack the incoming potato into the box. If the total weight of the potatoes in the box is now $X$ or greater, seal that box and prepare a new empty box.

You are given $Q$ queries. In the $i$-th query $(1 \leq i \leq Q)$, given a positive integer $K_i$, find the number of potatoes in the $K_i$-th box to be sealed. It can be proved that, under the Constraints of the problem, there will be at least $K_i$ sealed boxes.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $Q$ $X$

$W_0$ $W_1$ $\ldots$ $W_{N-1}$

$K_1$

$\vdots$

$K_Q$

Output

Print $Q$ lines. The $i$-th line $(1 \leq i \leq Q)$ should contain the answer to the $i$-th query.

Sample Input 1

3 2 5
3 4 1
1
2

Sample Output 1

2
3

Before sealing the $2$-nd box, Takahashi will do the following:

• Prepare an empty box.
• Pack the $1$-st potato into the box. Now, the total weight of potatoes in the box is $3$.
• Pack the $2$-nd potato into the box. Now, the total weight of potatoes in the box is $3 + 4 = 7$, which is not less than $X = 5$, so seal this box.
• Prepare a new empty box.
• Pack the $3$-rd potato into the box. Now, the total weight of potatoes in the box is $1$.
• Pack the $4$-th potato into the box. Now, the total weight of potatoes in the box is $1 + 3 = 4$.
• Pack the $5$-th potato into the box. Now, the total weight of potatoes in the box is $1 + 3 + 4 = 8$, which is not less than $X = 5$, so seal this box.

The $1$-st box sealed contains $2$ potatoes, and the $2$-nd box sealed contains $3$ potatoes.

Sample Input 2

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

Sample Output 2

4
5
5
5
5

update @ 2024/3/10 10:57:58