AT_abc258_e [ABC258E] Packing Potatoes

[problemUrl]: https://atcoder.jp/contests/abc258/tasks/abc258_e ベルトコンベアに載って $ 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/A

N/A

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