题目描述

给定序列 $W$，下标范围为 $[0, n - 1]$。存在一个长度为 $10^{100}$ 的土豆序列，循环节为 $n$，第 $i$ 个土豆的重量为 $W_{(i - 1) \bmod{n}}$。现在你需要用箱子装土豆，每个箱子装满则停止，即土豆重量恰好大于等于 $X$ 时则停止。$Q$ 组询问求第 $k_i$ 个箱子装了多少个土豆。

输入格式

第一行输入 $N$ $Q$ $X$

第二行输入 $W_0$ $W_1$ $\ldots$ $W_{N-1}$

接下来 $Q$ 行每行一个整数 $K_i$

输出格式

输出一共输出 $Q$ 行

3 2 5
3 4 1
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) $

样例 1 解释

土豆序列是 $[3, 4, 1, 3, 4, 1, 3, 4, 1, 3, 4, 1, \cdots]$，每个人都会装走刚好大于等与 $5$ 的土豆。

• 第一个人装走了 [3, 4]，带走 $2$ 颗土豆。
• 第二个人装走了 [1, 3, 4]，带走 $3$ 颗土豆。