B"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, ... , 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, ... , 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) 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. 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 = overline{x_{n-1} ldots x_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 = overline{z_{n-1} ... z_0} in binary, then this means to set f(z_0, ... , z_{n-1}) to 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, |"...