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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class F implements Runnable{
	public static void main (String[] args) {new Thread(null, new F(), "fuuuuuuck me", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		//i think both players always make different choices
		//or their choices are irrelevant so it's probably
		//just sum / 2^n
		//probably wrong though
		
		int n = fs.nextInt();
		int r = fs.nextInt();
		int[] a = new int[1 << n];
		long sum = 0;
		for(int i = 0; i < 1 << n; i++) {
			a[i] = fs.nextInt();
			sum += a[i];
		}
		double den = 1<<n;
		out.printf("%.7f\n", sum/den);
		for(int i = 0; i < r; i++) {
			int x = fs.nextInt();
			int v = fs.nextInt();
			sum -= a[x];
			a[x] = v;
			sum += a[x];
			out.printf("%.7f\n", sum/den);
		}

		out.close();
	}

	void sort (int[] a) {
		int n = a.length;
		for(int i = 0; i < 50; i++) {
			Random r = new Random();
			int x = r.nextInt(n), y = r.nextInt(n);
			int temp = a[x];
			a[x] = a[y];
			a[y] = temp;
		}
		Arrays.sort(a);
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}