配点 : $500$ 点

問題文

ベルトコンベアに載って $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$ 個以上存在することが証明できます。

制約

• $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$ 番目のクエリへの答えを出力せよ。

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