D. Игра
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аллен и Бесси играют в простую игру с числами. Они оба знают функцию $$$f: \{0, 1\}^n \to \mathbb{R}$$$, т.е. функцию, которая принимает $$$n$$$ бинарных аргументов и возвращает вещественное значение. В начале игры все переменные $$$x_1, x_2, \dots, x_n$$$ равны $$$-1$$$. В каждом раунде независимо с равной вероятностью ходит Аллен или Бесси. Ход состоит из выбора такого $$$i$$$, что $$$x_i = -1$$$ и либо установке $$$x_i \to 0$$$ либо $$$x_i \to 1$$$.

После $$$n$$$ раундов все переменные установлены, и результатом игры становится величина $$$f(x_1, x_2, \dots, x_n)$$$. Аллен хочет максимизировать результат, а Бесси — минимизировать его.

Ваша задача — помочь Аллену и Бесси определить математическое ожидание результата игры! Они сыграют $$$r+1$$$ раз, и между играми будет меняться ровно одно значение $$$f$$$. Другими словами, между играми $$$i$$$ и $$$i+1$$$ для $$$1 \le i \le r$$$, будет изменено значение $$$f(z_1, \dots, z_n) \to g_i$$$ для некоторого набора $$$(z_1, \dots, z_n) \in \{0, 1\}^n$$$. Найдите математическое ожидание результата в начале, а также после каждого изменения.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$r$$$ ($$$1 \le n \le 18$$$, $$$0 \le r \le 2^{18}$$$).

Следующая строка содержит $$$2^n$$$ целых чисел $$$c_0, c_1, \dots, c_{2^n-1}$$$ ($$$0 \le c_i \le 10^9$$$), обозначающих начальные значения функции $$$f$$$. Формально $$$f(x_0, x_1, \dots, x_{n-1}) = c_x$$$, если $$$x = \overline{x_{n-1} \ldots x_0}$$$ в двоичной записи.

Каждая из следующих $$$r$$$ строк содержит два целых числа $$$z$$$ и $$$g$$$ ($$$0 \le z \le 2^n - 1$$$, $$$0 \le g \le 10^9$$$). Если $$$z = \overline{z_{n-1} \dots z_0}$$$ в двоичной записи, то это означает изменение значения $$$f(z_0, \dots, z_{n-1}) \to g$$$.

Выходные данные

Выведите $$$r+1$$$ строку, в $$$i$$$-й строку должно находиться математическое ожидание результата $$$f$$$ в $$$i$$$-й игре. Ваш ответ должен иметь абсолютную или относительную ошибку не более $$$10^{-6}$$$.

Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Примеры
Входные данные
2 2
0 1 2 3
2 5
0 4
Выходные данные
1.500000
2.250000
3.250000
Входные данные
1 0
2 3
Выходные данные
2.500000
Входные данные
2 0
1 1 1 1
Выходные данные
1.000000
Примечание

Рассмотрим второй пример. Если первым сходит Аллен, то он положит $$$x_1 \to 1$$$, поэтому результат будет $$$3$$$. Если сходит Бесси, то она положит $$$x_1 \to 0$$$, и результат будет равен $$$2$$$. Поэтому ответ равен $$$2.5$$$.

В третьем примере результатом игры всегда будет $$$1$$$ независимо от игры Аллен и Бесси.