[ABC292Ex] Rating Estimator

你要参加 $n$ 场比赛。 如果第 $i$ 场比赛你的成绩为 $p_i$，那你的 rating 在第 $k$ 场比赛后将会变为前 $k$ 场比赛成绩的平均值，也就是$\frac{1}{k}(\sum^{k}_{i=1}p_i)$。 不过，如果在某场比赛后，你的 rating 大于等于一个值 $B$，它以后将不会在变化。 你对你每场比赛的成绩做了估计，你估计第 $i$ 场比赛你的成绩为 $a_i$。 现在有 $q$ 组询问，每组询问中给出两个数 $c$ 和 $x$，表示将第 $c$ 场比赛的成绩修改为 $x$（注意这一操作在此后的询问中会被保留），输出修改之后，如果你每场比赛的真实成绩都与预估的一样，你在第 $n$ 场比赛后的 rating。

[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} $ 以下であれば正解として扱われる。

5 6 7
5 1 9 3 8
4 9
2 10
1 0
3 0
3 30
5 100
1 100

6.000000000000000
7.500000000000000
6.333333333333333
5.400000000000000
13.333333333333334
13.333333333333334
100.000000000000000

### 制約 - $ 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 行目にはこれを出力します。