Problem: Allen and Bessie are playing a simple number game. They both know a function f: \{0, 1\}^n → 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 → 0 or x_i → 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) → g_i for some (z_1, ..., z_n) ∈ \{0, 1\}^n. You are to find the expected game value in the beginning and after each change.

Input

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} … 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}) → g.

Output

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}.

Examples

Input

2 2
0 1 2 3
2 5
0 4


Output

1.500000
2.250000
3.250000


Input

1 0
2 3


Output

2.500000


Input

2 0
1 1 1 1


Output

1.000000

Note

Consider the second test case. If Allen goes first, he will set x_1 → 1, so the final value will be 3. If Bessie goes first, then she will set x_1 → 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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
void readi(T &x) {
  T input = 0;
  bool negative = false;
  char c = ' ';
  while (c < '-') {
    c = getchar();
  }
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  while (c >= '0') {
    input = input * 10 + (c - '0');
    c = getchar();
  }
  if (negative) {
    input = -input;
  }
  x = input;
}
template <class T>
void printi(T output) {
  if (output == 0) {
    putchar('0');
    return;
  }
  if (output < 0) {
    putchar('-');
    output = -output;
  }
  int aout[20];
  int ilen = 0;
  while (output) {
    aout[ilen] = ((output % 10));
    output /= 10;
    ilen++;
  }
  for (int i = ilen - 1; i >= 0; i--) {
    putchar(aout[i] + '0');
  }
  return;
}
template <class T>
void ckmin(T &a, T b) {
  a = min(a, b);
}
template <class T>
void ckmax(T &a, T b) {
  a = max(a, b);
}
long long randomize(long long mod) {
  return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;
long long normalize(long long x, long long mod = 1000000007) {
  return (((x % mod) + mod) % mod);
}
int N, Q;
long long arr[2000013];
long long sum = 0;
int32_t main() {
  ios_base::sync_with_stdio(0);
  srand(time(0));
  cout << fixed << setprecision(12);
  cerr << fixed << setprecision(12);
  if (fopen("cf995d.in", "r")) {
    freopen("cf995d.in", "r", stdin);
    freopen("cf995d.out", "w", stdout);
  }
  cin >> N >> Q;
  for (int i = 0; i < (1 << N); i++) {
    cin >> arr[i];
    sum += arr[i];
  }
  cout << 1.0 * sum / (1 << N) << '\n';
  while (Q--) {
    int idx;
    long long val;
    cin >> idx >> val;
    sum += (val - arr[idx]);
    arr[idx] = val;
    cout << 1.0 * sum / (1 << N) << '\n';
  }
  return 0;
}