题目描述

一条传送带上的$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$个查询的答案。

示例输入1

3 2 5
3 4 1
1
2

示例输出1

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$个土豆。

示例输入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