说明

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

输入格式

第一行三个整数 $n, B, q$。

第二行 $n$ 个整数 $a_i$。

接下来 $q$ 行，每行两个整数 $c_i, x_i$。

输出格式

对于每次询问，输出对应的答案，保留 $15$ 位小数

样例

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\ 1\ \leq\ 10^5 $，$ 0\ \leq\ a_i\ \leq\ 10^9 $，$ 1\ \leq\ c\ \leq\ N $，$ 0\ \leq\ x\ \leq\ 10^9 $。