CF995D.Game

Allen and Bessie are playing a simple number game. They both know a function $f: {0, 1}^n \to \mathbb{R}$, i. e. the function takes $n$ binary arguments and returns a real value. At the start of the game, the variables $x_1, x_2, \dots, x_n$ are all set to $-1$. Each round, with equal probability, one of Allen or Bessie gets to make a move. A move consists of picking an $i$ such that $x_i = -1$ and either setting $x_i \to 0$ or $x_i \to 1$.

After $n$ rounds all variables are set, and the game value resolves to $f(x_1, x_2, \dots, x_n)$. Allen wants to maximize the game value, and Bessie wants to minimize it.

Your goal is to help Allen and Bessie find the expected game value! They will play $r+1$ times though, so between each game, exactly one value of $f$ changes. In other words, between rounds $i$ and $i+1$ for $1 \le i \le r$, $f(z_1, \dots, z_n) \to g_i$ for some $(z_1, \dots, z_n) \in {0, 1}^n$. You are to find the expected game value in the beginning and after each change.

艾伦和贝西正在玩一个简单的数字游戏。他们都知道一个函数 $f: {0, 1}^n \to \mathbb{R}$，即该函数接收 $n$ 个二进制输入，并返回一个实数值。游戏开始时，变量 $x_1, x_2, \dots, x_n$ 均被设为 $-1$。每一轮中，艾伦和贝西以相等的概率之一获得行动权。一次行动包括：选择一个满足 $x_i = -1$ 的下标 $i$，并将 $x_i$ 设为 $0$ 或 $1$。

经过 $n$ 轮后，所有变量均被赋值，游戏结果即为 $f(x_1, x_2, \dots, x_n)$。艾伦希望最大化游戏结果，而贝西希望最小化它。

你的目标是帮助艾伦和贝西求出游戏的期望结果！不过，他们将共进行 $r+1$ 局游戏；而在每两局之间，函数 $f$ 恰好有一个取值发生改变。换言之，在第 $i$ 局与第 $i+1$ 局之间（其中 $1 \le i \le r$），存在某个 $(z_1, \dots, z_n) \in {0, 1}^n$，使得 $f(z_1, \dots, z_n)$ 的值变为 $g_i$。你需要依次求出初始状态以及每次修改后的期望游戏结果。

The first line contains two integers $n$ and $r$ ($1 \le n \le 18$, $0 \le r \le 2^{18}$).

The next line contains $2^n$ integers $c_0, c_1, \dots, c_{2^n-1}$ ($0 \le c_i \le 10^9$), denoting the initial values of $f$. More specifically, $f(x_0, x_1, \dots, x_{n-1}) = c_x$, if $x = \overline{x_{n-1} \ldots x_0}$ in binary.

Each of the next $r$ lines contains two integers $z$ and $g$ ($0 \le z \le 2^n - 1$, $0 \le g \le 10^9$). If $z = \overline{z_{n-1} \dots z_0}$ in binary, then this means to set $f(z_0, \dots, z_{n-1}) \to g$.

第一行包含两个整数 $n$ 和 $r$（$1 \le n \le 18$，$0 \le r \le 2^{18}$）。

第二行包含 $2^n$ 个整数 $c_0, c_1, \dots, c_{2^n-1}$（$0 \le c_i \le 10^9$），表示函数 $f$ 的初始值。更具体地，若 $x = \overline{x_{n-1} \ldots x_0}$ 为其二进制表示，则 $f(x_0, x_1, \dots, x_{n-1}) = c_x$。

接下来的 $r$ 行中，每行包含两个整数 $z$ 和 $g$（$0 \le z \le 2^n - 1$，$0 \le g \le 10^9$）。若 $z = \overline{z_{n-1} \dots z_0}$ 为其二进制表示，则该操作表示将 $f(z_0, \dots, z_{n-1})$ 的值更新为 $g$。

Print $r+1$ lines, the $i$-th of which denotes the value of the game $f$ during the $i$-th round. Your answer must have absolute or relative error within $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.

输出 $r+1$ 行，其中第 $i$ 行表示游戏 $f$ 在第 $i$ 轮的值。你的答案必须满足绝对误差或相对误差在 $10^{-6}$ 以内。

形式化地，设你的答案为 $a$，评测机的答案为 $b$。若 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$，则你的答案被视为正确。

Consider the second test case. If Allen goes first, he will set $x_1 \to 1$, so the final value will be $3$. If Bessie goes first, then she will set $x_1 \to 0$ so the final value will be $2$. Thus the answer is $2.5$.

In the third test case, the game value will always be $1$ regardless of Allen and Bessie's play.

考虑第二个测试用例。如果 Allen 先手，他将设置 $x_1 \to 1$，因此最终值为 $3$；如果 Bessie 先手，则她将设置 $x_1 \to 0$，因此最终值为 $2$。因此答案为 $2.5$。

在第三个测试用例中，无论 Allen 和 Bessie 如何操作，游戏的值恒为 $1$。