Problem: Drazil likes heap very much. So he created a problem with heap:

There is a max heap with a height h implemented on the array. The details of this heap are the following:

This heap contains exactly 2^h - 1 distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array a indexed from 1 to 2^h-1. For any 1 < i < 2^h, a[i] < a[\left ⌊{i/2}\right ⌋].

Now we want to reduce the height of this heap such that the height becomes g with exactly 2^g-1 numbers in heap. To reduce the height, we should perform the following action 2^h-2^g times:

Choose an index i, which contains an element and call the following function f in index i:

<image>

Note that we suppose that if a[i]=0, then index i don't contain an element.

After all operations, the remaining 2^g-1 element must be located in indices from 1 to 2^g-1. Now Drazil wonders what's the minimum possible sum of the remaining 2^g-1 elements. Please find this sum and find a sequence of the function calls to achieve this value.

Input

The first line of the input contains an integer t (1 ≤ t ≤ 70 000): the number of test cases.

Each test case contain two lines. The first line contains two integers h and g (1 ≤ g < h ≤ 20). The second line contains n = 2^h-1 distinct positive integers a[1], a[2], …, a[n] (1 ≤ a[i] < 2^{20}). For all i from 2 to 2^h - 1, a[i] < a[\left ⌊{i/2}\right ⌋].

The total sum of n is less than 2^{20}.

Output

For each test case, print two lines.

The first line should contain one integer denoting the minimum sum after reducing the height of heap to g. The second line should contain 2^h - 2^g integers v_1, v_2, …, v_{2^h-2^g}. In i-th operation f(v_i) should be called.

Example

Input


2
3 2
7 6 3 5 4 2 1
3 2
7 6 5 4 3 2 1


Output


10
3 2 3 1
8
2 1 3 1

Solution (in JAVA):

Solution:
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;


import java.util.Random;
import java.util.TreeSet;

public final class CF_631_D2_E
{


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputFlush(Object o){try {out.write(""+ o+"\n");out.flush();} catch (Exception e) {}}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}



	// Global vars
	static BufferedWriter out;
	static InputReader reader;






	static int pgcd(int a,int b) {
		if (a<b)
			return pgcd(b,a);
		while (b>0) {
			int c=b;
			b=a%b;
			a=c;
		}
		return a;

	}

	static long pgcd(long a,long b) {
		if (a<b)
			return pgcd(b,a);
		while (b>0) {
			long c=b;
			b=a%b;
			a=c;
		}
		return a;

	}



	static void test() {
		log("testing");

		Random r=new Random();
		int NTESTS=100000;
		int NMAX=100;
		for (int t=0;t<NTESTS;t++) {

		}

		log("done");

	}

	static int st;
	
	static void explore(int[] dest,int x,int[] a) {
		int n=a.length;
		//log("st:"+st+" x:"+x+" n:"+n+" dest.length:"+dest.length);
		dest[st++]=a[x-1];
		if (2*x<=n)
			explore(dest,2*x,a);
		if (2*x+1<=n)
			explore(dest,2*x+1,a);
	}

	static void solveKO(int h,int g,int[] a) {
		int n=a.length;
		int m=(1<<g)-1;
		int min=Integer.MAX_VALUE;
		if (m==1) {
			for (int i=0;i<n;i++) {
				min=Math.min(min, a[i]);
			}
			output(min);
			for (int i=0;i<n-m;i++)
				outputWln("1 ");
			output("");
			return;
		}
		//log("m:"+m);
		// we need m elements
		int hl=n/2;
		int[] half1=new int[hl];
		int[] half2=new int[hl];
		st=0;
		explore(half1,2,a);
		st=0;
		explore(half2,3,a);

		Arrays.sort(half1);
		Arrays.sort(half2);


		long sum=Long.MAX_VALUE;

		int cur1=hl-1;
		int cur2=hl-1;
		int[] ans=new int[n-m];
		int hg=m/2;
		//log("hl:"+hl);
		long bob=a[0];
		for (int i=0;i<n-m;i++) {
			//log("cur1:"+cur1+" cur2:"+cur2+" // "+half1.length+" "+half2.length);
			if (half1[cur1]>half2[cur2]) {
				if (cur1>=hg) {
					bob=half1[cur1];
					cur1--;
					ans[i]=1;
					log("removing top");
				} else {

					log("removing "+half2[cur2]);
					cur2--;
					ans[i]=3;
				}
				// this is top 
			} else {
				if (cur2>=hg) {
					log("removing top");
					bob=half2[cur2];
					cur2--;
					ans[i]=1;
				} else {

					log("removing "+half1[cur1]);

					cur1--;
					ans[i]=2;
				}
			}
			log("top:"+bob);
		}
		for (int i=0;i<=cur1;i++) {
			logWln(half1[i]+" ");
			bob+=half1[i];
		}
		log("");

		for (int i=0;i<=cur2;i++) {
			bob+=half2[i];
			logWln(half2[i]+" ");

		}
		log("");
		output(bob);

		for (int x:ans)
			outputWln(x+" ");
		output("");

	}


	static boolean cache[];
	static int[] visited;


	static boolean canDo(int n,int m,int[] a,int node) {
		boolean ans=true;
		if (a[node-1]==0) {
			ans=false;
		} else {
			int left=2*node;
			int right=2*node+1;
			if (right<=n) {
				if (node>m) {
					ans=true;
				} else 
					if (node==m) {
						ans=a[left-1]!=0 || a[right-1]!=0;
					} else {
						// now node<m
						if (a[left-1]>a[right-1])
							ans=canDo(n,m,a,left);
						else
							ans=canDo(n,m,a,right);
					}
			} else {
				// always ok, as we are supposed to have n<m, so can always remove last rank
			}
		}
		//cache[node-1]=ans;
		return ans;
	}
	
	static void execute(int n,int[] a,int node) {
		int left=2*node;
		int right=2*node+1;
		if (right>n) {
			//log("node:"+node+" case 1 // right:"+right+" n:"+n);
			a[node-1]=0;
			return;
		}
		if (a[left-1]>a[right-1]) {
			//log("node:"+node+" case 2left");
			a[node-1]=a[left-1];
			execute(n,a,left);
		}
		else {
			//log("node:"+node+" case 2right");
			a[node-1]=a[right-1];
			execute(n,a,right);
		}
	}

	static int[] moves;
	
	static void solveRec(int n,int m,int[] a,int node) {
		while (canDo(n,m,a,node)) {
			execute(n,a,node);
			//log(a);
			moves[st++]=node;
		}
		if (2*node+1<=n) {
			solveRec(n,m,a,2*node);
			solveRec(n,m,a,2*node+1);
		}
	}
		
	static void solve(int n,int m,int[] a) {
		moves=new int[n-m];
		st=0;
		solveRec(n,m,a,1);
		long sum=0;
		for (int i=0;i<m;i++) {
			sum+=a[i];
		}
		output(sum);
		for (int x:moves)
			outputWln(x+" ");
		output("");
		//log(a);
	}
	

	/*
	static void solve(int n,int m,int[] a) {
		
		solvePart(a,2,n,m,true);
		int topL1=top;
		int[] mov1=moves;
		
		solvePart(a,2,n,m,false);
		int topL2=top;
		int[] mov2=moves;
		

	}
	*/

	static void process() throws Exception {

		//log("hello");

		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);

		//testAll(20);



		int T=reader.readInt();
		for (int t=0;t<T;t++) {
			//log("--------------");
			int h=reader.readInt();
			int g=reader.readInt();
			int n=(1<<h)-1;
			int m=(1<<g)-1;
			
			int[] a=new int[n];
			for (int i=0;i<n;i++)
				a[i]=reader.readInt();
			solve(n,m,a);


		}

		try {
			out.close();
		} catch (Exception Ex) {
		}

	}





	public static void main(String[] args) throws Exception {
		process();

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final String readString(int L) throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder(L);
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}
/*

5
1 4 5 2 3

 */