{"raw_statement":[{"iden":"problem statement","content":"You will participate in $N$ contests, numbered $1$ to $N$ in chronological order.  \nA participant in each contest will be given a value called **performance** for that contest. Let $P_i$ be the performance for contest $i$.  \nAdditionally, you have a value called **rating**, which changes according to the performances in contests. The initial rating is $0$, and the rating after contest $n$ is $\\frac{1}{n} \\left(\\sum_{i=1}^n P_i \\right)$.  \nHowever, once your rating is $B$ **or higher**, later contests will not affect your rating.\nBefore the contests, you have decided to estimate your performance in each contest. Let $a_i$ be the initial estimate of your performance in contest $i$. Process $Q$ queries in the order they are given.\nIn each query, you are given two integers $c$ and $x$. First, change the estimate of your performance in contest $c$ to $x$. (This change is persistent.) Then, assuming that you get the estimated performances in all $N$ contests, print your final rating after the contests."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5 \\times 10^5$\n*   $1 \\leq B \\leq 10^9$\n*   $1 \\leq Q \\leq 10^5$\n*   $0 \\leq a_i \\leq 10^9$\n*   $1 \\leq c \\leq N$\n*   $0 \\leq x \\leq 10^9$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format, where $c_i$ and $x_i$ are the $c$ and $x$ for the $i$\\-th query:\n\n$N$ $B$ $Q$\n$a_1$ $a_2$ $\\dots$ $a_N$\n$c_1$ $x_1$\n$c_2$ $x_2$\n$\\vdots$\n$c_Q$ $x_Q$"},{"iden":"sample input 1","content":"5 6 7\n5 1 9 3 8\n4 9\n2 10\n1 0\n3 0\n3 30\n5 100\n1 100"},{"iden":"sample output 1","content":"6.000000000000000\n7.500000000000000\n6.333333333333333\n5.400000000000000\n13.333333333333334\n13.333333333333334\n100.000000000000000\n\nInitially, $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8)$.  \nThe first query changes $a_4$ to $9$, making $(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8)$.  \nHere, assuming that your performance in contest $i$ is $a_i$, your rating will change as follows.\n\n*   Initially, your rating is $0$.\n*   After contest $1$, your rating will be $5 / 1 = 5$.\n*   After contest $2$, your rating will be $(5 + 1) / 2 = 3$.\n*   After contest $3$, your rating will be $(5 + 1 + 9) / 3 = 5$.\n*   After contest $4$, your rating will be $(5 + 1 + 9 + 9) / 4 = 6$.\n*   Your rating will no longer change, because your rating after contest $4$ is not less than $B$.\n\nThus, your final rating after the contests is $6$, which should be printed in the first line."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}