题目描述

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

题目大意

你要参加 $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。

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