问题描述

您将参加 $N$ 场比赛，编号为 $1$ 到 $N$，按时间顺序依次进行。
每场比赛的参与者都会获得一个称为 表现 的值。设 $P_i$ 为第 $i$ 场比赛的表现。
此外，您还有一个称为 评级 的值，根据比赛表现而变化。初始评级为 $0$，第 $n$ 场比赛后的评级为 $\\frac{1}{n} \\left(\\sum_{i=1}^n P_i \\right)$。
但是，一旦您的评级达到或超过 $B$，后面的比赛将不会影响您的评级。

在比赛开始之前，您已经决定估计自己在每场比赛中的表现。设 $a_i$ 是您对第 $i$ 场比赛的初始估计。按照给定的顺序处理 $Q$ 个查询。

在每个查询中，给定两个整数 $c$ 和 $x$。首先，将第 $c$ 场比赛中的表现估计更改为 $x$。（此更改是持久的。）然后，假设您获得了所有 $N$ 场比赛的估计表现，打印出比赛结束后的最终评级。

约束条件

• $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$
• 输入中的所有值都为整数。

输入

输入以以下格式从标准输入给出，其中 $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

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

示例输出 1

6.000000000000000
7.500000000000000
6.333333333333333
5.400000000000000
13.333333333333334
13.333333333333334
100.000000000000000

开始时，$(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8)$。
第一个查询将 $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$，应该在第一行打印出来。