Multidimensional Expectations

Alice and Bob 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,...,x_n$ are all set to $-1$. Each round, with equal probability, one of Alice or Bob 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,...,x_n)$. Alice wants to maximize the game value, and Bob wants to minimize it.

Your goal is to help Alice and Bob 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,...,z_n)\to g_i$ for some $(z_1,...,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,...,c_{2^n-1}(0\le c_i\le 10^9)$, denoting the initial values of $f$. More specifically, $f(x_0,x_1,...,x_{n-1})=c_x$, if $x=\overline{x_{n-1}...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}...z_0}$ in binary, then this means to set $f(z_0,...,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

Consider the second test case. If Alice goes first, she will set $x_1\to 1$, so the final value will be $3$. If Bob goes first, then he 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 Alice and Bob's play.