You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

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

题目描述

ベルトコンベアに載って $10^{100}$ 個のじゃがいもが $1$ 個ずつ流れてきます。流れてくるじゃがいもの重さは長さ $N$ の数列 $W\ =\ (W_0,\ \dots,\ W_{N-1})$ で表され、$i\ \,\ (1\ \leq\ i\ \leq\ 10^{100})$ 番目に流れてくるじゃがいもの重さは $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$ $\ldots$ $W_{N-1}$ $K_1$ $\vdots$ $K_Q$

输出格式

$Q$ 行出力せよ。$i\ \,\ (1\ \leq\ i\ \leq\ Q)$ 行目には、$i$ 番目のクエリへの答えを出力せよ。

样例 #1

样例输入 #1

3 2 5
3 4 1
1
2

样例输出 #1

2
3

样例 #2

样例输入 #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

提示

制約

• $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)$
• 入力は全て整数

Sample Explanation 1

$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$ つのじゃがいもが入っています。