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.


-----Input-----

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$.


-----Output-----

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}$.


-----Examples-----
Input
2 2
0 1 2 3
2 5
0 4

Output
1.500000
2.250000
3.250000

Input
1 0
2 3

Output
2.500000

Input
2 0
1 1 1 1

Output
1.000000



-----Note-----

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.

Difficulty: VERY_HARD
Tags: Mathematics

Starter code:

Solutions:
(n, r) = [int(x) for x in input().split()]
n = 2 ** n
xs = [int(x) for x in input().split()]
s = sum(xs)
res = [0 for _ in range(r + 1)]
for i in range(r):
	res[i] = s / n
	(i, val) = [int(x) for x in input().split()]
	s += val - xs[i]
	xs[i] = val
res[r] = s / n
print('\n'.join(map(str, res)))


import sys
(n, r) = [int(x) for x in sys.stdin.readline().split()]
a = [int(x) for x in sys.stdin.readline().split()]
s = sum(a)
n = 2 ** n
sys.stdout.write(str(s / n) + '\n')
for i in range(r):
	(p, x) = [int(x) for x in sys.stdin.readline().split()]
	s = s - a[p] + x
	a[p] = x
	sys.stdout.write(str(s / n) + '\n')


R = lambda : list(map(int, input().split()))
sum1 = 0
p1 = 1
a = [0] * 263000
b = a
(n, r) = R()
p1 = 2 ** n
a = R()
sum1 = sum(a)
p2 = sum1 / p1
for i in range(r):
	(z, g) = R()
	sum1 = sum1 - a[z] + g
	a[z] = g
	b[i] = sum1 / p1
print(p2)
for i in range(r):
	print(b[i])


from sys import stdin
from math import fsum

def main():
	(n, m) = map(int, input().split())
	ff = list(map(float, input().split()))
	(scale, r) = (0.5 ** n, fsum(ff))
	res = [r * scale]
	for (si, sf) in map(str.split, stdin.read().splitlines()):
		(i, f) = (int(si), float(sf))
		r += f - ff[i]
		ff[i] = f
		res.append(r * scale)
	print('\n'.join(map(str, res)))
main()


import time
(n, r) = (int(i) for i in input().split())
c = [int(i) for i in input().split()]
start = time.time()
s = sum(c)
n2 = 2 ** n
ans = [s / n2]
for i in range(r):
	(k, new) = (int(i) for i in input().split())
	s += new - c[k]
	c[k] = new
	ans.append(s / n2)
for i in range(len(ans)):
	print(ans[i])
finish = time.time()