E - Packing Potatoes 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

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

入力例 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

Score : 500 points

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