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>
#pragma warning(disable : 4996)
using namespace std;
namespace Xrocks {}
using namespace Xrocks;
namespace Xrocks {
class in {
} user_input;
class out {
} output;
in& operator>>(in& X, int& Y) {
  scanf("%d", &Y);
  return X;
}
in& operator>>(in& X, char* Y) {
  scanf("%s", Y);
  return X;
}
in& operator>>(in& X, float& Y) {
  scanf("%f", &Y);
  return X;
}
in& operator>>(in& X, double& Y) {
  scanf("%lf", &Y);
  return X;
}
in& operator>>(in& X, char& C) {
  scanf("%c", &C);
  return X;
}
in& operator>>(in& X, string& Y) {
  cin >> Y;
  return X;
}
in& operator>>(in& X, long long& Y) {
  scanf("%lld", &Y);
  return X;
}
template <typename T>
in& operator>>(in& X, vector<T>& Y) {
  for (auto& x : Y) user_input >> x;
  return X;
}
template <typename T>
out& operator<<(out& X, const T& Y) {
  cout << Y;
  return X;
}
template <typename T>
out& operator<<(out& X, vector<T>& Y) {
  for (auto& x : Y) output << x << " ";
  return X;
}
out& operator<<(out& X, const int& Y) {
  printf("%d", Y);
  return X;
}
out& operator<<(out& X, const char& C) {
  printf("%c", C);
  return X;
}
out& operator<<(out& X, const string& Y) {
  printf("%s", Y.c_str());
  return X;
}
out& operator<<(out& X, const long long& Y) {
  printf("%lld", Y);
  return X;
}
out& operator<<(out& X, const float& Y) {
  printf("%f", Y);
  return X;
}
out& operator<<(out& X, const double& Y) {
  printf("%lf", Y);
  return X;
}
out& operator<<(out& X, const char Y[]) {
  printf("%s", Y);
  return X;
}
template <typename T>
T max(T A) {
  return A;
}
template <typename T, typename... args>
T max(T A, T B, args... S) {
  return max(A > B ? A : B, S...);
}
template <typename T>
T min(T A) {
  return A;
}
template <typename T, typename... args>
T min(T A, T B, args... S) {
  return min(A < B ? A : B, S...);
}
template <typename T>
void vectorize(int y, vector<T>& A) {
  A.resize(y);
}
template <typename T, typename... args>
void vectorize(int y, vector<T>& A, args&&... S) {
  A.resize(y);
  vectorize(y, S...);
}
long long fast(long long a, long long b, long long pr) {
  if (b == 0) return 1 % pr;
  long long ans = 1 % pr;
  while (b) {
    if (b & 1) ans = (ans * a) % pr;
    b >>= 1;
    a = (a * a) % pr;
  }
  return ans;
}
int readInt() {
  int n = 0;
  int ch = getchar_unlocked();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar_unlocked();
  }
  while (ch >= '0' && ch <= '9')
    n = (n << 3) + (n << 1) + ch - '0', ch = getchar_unlocked();
  n = n * sign;
  return n;
}
long long readLong() {
  long long n = 0;
  int ch = getchar_unlocked();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar_unlocked();
  }
  while (ch >= '0' && ch <= '9')
    n = (n << 3) + (n << 1) + ch - '0', ch = getchar_unlocked();
  n = n * sign;
  return n;
}
long long inv_(long long val,
               long long pr = static_cast<long long>(998244353)) {
  return fast(val, pr - 2, pr);
}
}  // namespace Xrocks
class solve {
  vector<long long> v;

 public:
  solve() {
    int n, r;
    user_input >> n >> r;
    v.resize(1 << n);
    user_input >> v;
    long long sumz = accumulate(v.begin(), v.end(), 0LL);
    long double d = (1 << n);
    printf("%.9lf\n", static_cast<double>(sumz / d));
    for (int i = 0; i < r; i++) {
      long long pos, val;
      user_input >> pos >> val;
      sumz -= v[pos];
      v[pos] = val;
      sumz += v[pos];
      printf("%.9lf\n", static_cast<double>(sumz / d));
    }
  }
};
int32_t main() {
  int t = 1, i = 1;
  if (0 || 0) scanf("%d", &t);
  while (t--) {
    if (0) printf("Case #%d: ", i++);
    new solve;
  }
  return 0;
}