D. Gametime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAllen 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.InputThe 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.OutputPrint 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}.ExamplesInput2 20 1 2 32 50 4Output1.5000002.2500003.250000Input1 02 3Output2.500000Input2 01 1 1 1Output1.000000NoteConsider 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.
Input2 20 1 2 32 50 4
Output1.5000002.2500003.250000
['math', '*2500']