write a go solution for Description:
Allen and Bessie are playing a simple number game. They both know a function f:0,1^ntomathbbR, 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 Allen or Bessie gets to make a move. A move consists of picking an i such that x_i=-1 and either setting x_ito0 or x_ito1.

After n rounds all variables are set, and the game value resolves to f(x_1,x_2,...,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<=i<=r, f(z_1,...,z_n)tog_i for some (z_1,...,z_n)in0,1^n. You are to find the expected game value in the beginning and after each change.

Input Format:
The first line contains two integers n and r (1<=n<=18, 0<=r<=2^18).

The next line contains 2^n integers c_0,c_1,...,c_2^n-1 (0<=c_i<=10^9), denoting the initial values of f. More specifically, f(x_0,x_1,...,x_n-1)=c_x, if x=overlinex_n-1ldotsx_0 in binary.

Each of the next r lines contains two integers z and g (0<=z<=2^n-1, 0<=g<=10^9). If z=overlinez_n-1...z_0 in binary, then this means to set f(z_0,...,z_n-1)tog.

Output Format:
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|)<=10^-6.

Note:
Consider the second test case. If Allen goes first, he will set x_1to1, so the final value will be 3. If Bessie goes first, then she will set x_1to0 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.. Output only the code with no comments, explanation, or additional text.