AT_abc292_h [ABC292Ex] Rating Estimator

[problemUrl]: https://atcoder.jp/contests/abc292/tasks/abc292_h あなたは $ N $ 個のコンテストに参加します。コンテストが開催される順にコンテスト $ 1 $, コンテスト $ 2 $, $ \dots $ コンテスト $ N $ と呼びます。 各コンテストに参加すると、コンテストごとに **パフォーマンス** という値が与えられます。コンテスト $ i $ で与えられるパフォーマンスを $ P_i $ とします。 また、あなたは **レーティング** という値を持っています。レーティングはコンテストでのパフォーマンスによって変化する値です。コンテストに参加する前のレーティングの値は $ 0 $ で、コンテスト $ n $ に出た後のレーティングの値は $ \frac{1}{n}\ \left(\sum_{i=1}^n\ P_i\ \right) $ に変化します。 ただし、あなたのレーティングが一度 $ B $ **以上** になると、それ以降はコンテストに参加してもレーティングは変動しなくなります。 あなたはコンテストに出る前に、それぞれのコンテストで得られるパフォーマンスを予測することにしました。はじめ、コンテスト $ i $ のパフォーマンスの予測値を $ a_i $ とします。クエリが $ Q $ 個与えられるので入力される順にすべて処理してください。 各クエリでは 2 個の整数 $ c,\ x $ が与えられます。あなたは、まずコンテスト $ c $ のパフォーマンスの予測値を $ x $ に変更します。(この変更は永続的です。) そして、あなたが $ N $ 個のコンテスト全てで現在の予測値通りのパフォーマンスを得られた場合の、全てのコンテストに参加した後のレーティングの値を答えてください。

入力は以下の形式で標準入力から与えられる。ただし、$ c_i,\ x_i $ は $ i $ 番目のクエリで与えられる $ c,\ x $ を意味する。 > $ N $ $ B $ $ Q $ $ a_1 $ $ a_2 $ $ \dots $ $ a_N $ $ c_1 $ $ x_1 $ $ c_2 $ $ x_2 $ $ \vdots $ $ c_Q $ $ x_Q $

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。 なお、真の値との絶対誤差または相対誤差が $ 10^{-9} $ 以下であれば正解として扱われる。

### 制約 - $ 1\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 1\ \leq\ B\ \leq\ 10^9 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 0\ \leq\ a_i\ \leq\ 10^9 $ - $ 1\ \leq\ c\ \leq\ N $ - $ 0\ \leq\ x\ \leq\ 10^9 $ - 入力される値はすべて整数 ### Sample Explanation 1 はじめ、$ (a_1,\ a_2,\ a_3,\ a_4,\ a_5)\ =\ (5,\ 1,\ 9,\ 3,\ 8) $ です。 1 番目のクエリによって $ a_4 $ が $ 9 $ に変更されて $ (a_1,\ a_2,\ a_3,\ a_4,\ a_5)\ =\ (5,\ 1,\ 9,\ 9,\ 8) $ となります。 このとき、コンテスト $ i $ でパフォーマンス $ a_i $ を取った場合のあなたのレーティングの推移は次の通りです。 - はじめ、レーティングは $ 0 $ です。 - コンテスト $ 1 $ が終了した時点でレーティングは $ 5\ /\ 1\ =\ 5 $ に変化します。 - コンテスト $ 2 $ が終了した時点でレーティングは $ (5\ +\ 1)\ /\ 2\ =\ 3 $ に変化します。 - コンテスト $ 3 $ が終了した時点でレーティングは $ (5\ +\ 1\ +\ 9)\ /\ 3\ =\ 5 $ に変化します。 - コンテスト $ 4 $ が終了した時点でレーティングは $ (5\ +\ 1\ +\ 9\ +\ 9)\ /\ 4\ =\ 6 $ に変化します。 - 以降、レーティングの値は変化しません。なぜならば、$ 4 $ 番目のコンテストが終了した時点でレーティングが $ B $ 以上の値になっているからです。 よって、全てのコンテストが終了した時点でのレーティングは $ 6 $ なので、1 行目にはこれを出力します。