Багатовимірні очікування

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

Після $n$ раундів всі змінні встановлені, і результатом гри стає $f(x_1,x_2,...,x_n)$. Аліса хоче максимізувати результат, а Боб хоче його мінімізувати.

Ваша мета — допомогти Алісі та Бобу знайти математичне сподівання результату гри! Вони будуть грати $r+1$ разів, і між іграми змінюється рівно одне значення $f$. Іншими словами, між раундами $i$ та $i+1$ для $1\le i\le r$, буде змінено значення $f(z_1,...,z_n)\to g_i$ для деякого набору $(z_1,...,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,...,c_{2^n-1}(0\le c_i\le 10^9)$, що позначають початкові значення функції $f$. Формально, $f(x_0,x_1,...,x_{n-1})=c_x$, якщо $x=\overline{x_{n-1}...x_0}$ у двійковому записі.

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

Вихідні дані

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

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

Приклади

Розглянемо другий тестовий випадок. Якщо Аліса піде першою, вона встановить $x_1\to 1$, так що остаточне значення буде $3$. Якщо Боб ходить першим, то він встановить $x_1\to 0$, так що остаточне значення буде дорівнювати $2$. Таким чином, відповідь дорівнює $2.5$.

У третьому наборі вхідних даних результат гри завжди буде дорівнювати $1$, незалежно від гри Аліси і Боба.