#include<bits/stdc++.h>
using namespace std;
namespace file_read{
	char ib[1<<24],*ip1=ib,*ip2=ib;
	inline char gc(){
		return ((ip1==ip2)&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin)),ip1==ip2?EOF:*ip1++);
	}
	inline int read(){
		int x=0;char c=gc();
		while(c<'0'||c>'9')c=gc();
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
		return x;
	}
	inline long long readl(){
		long long x=0;char c=gc();
		while(c<'0'||c>'9')c=gc();
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
		return x;
	}
}
using namespace file_read;
long long a[100005];
int n,m;
long long ann;
namespace yuchu{
	long long b[100005],c[100005];
	int z[100005];
	void solve(){
		for(int i=1;i<=n;++i)b[i]=a[i];
		long long ans=0;
		int ff=0;
		for(int t=59;t>=0;--t){
			int gs=0;
			for(int i=1;i<=n;++i)if(b[i]>>t&1)++gs;
			if(gs%2==0)continue;
			if(gs==n){
				ff=1;break;
			}
			long long T=(1ll<<(t+1))-1;
			long long mx=-1;int wz=0;
			for(int i=1;i<=n;++i){
				if((b[i]&T)>=(1ll<<t))continue;
				if(mx<(b[i]&T))mx=(b[i]&T),wz=i;
			}
			ans+=(1ll<<t)-mx;b[wz]+=(1ll<<t)-mx;
		}
		if(ff){
			ans=LLONG_MAX;
			for(int t=60;t>=1;--t){
				int gs=0;
				for(int i=1;i<=n;++i)if(a[i]>>t&1)++gs;
				if(gs%2)break;
				for(int i=1;i<=n;++i){
					c[i]=(a[i]&((1ll<<(t+1))-1));z[i]=i;
				}
				sort(z+1,z+n+1,[&](int x,int y){
					return c[x]<c[y];
				});
				int w=0;
				for(int i=1;i<=n;++i){
					if(c[z[i]]<(1ll<<t))w=i;
				}
				if(w>=2){
					for(int i=1;i<=n;++i)b[i]=a[i];
					int u=z[w-1],v=z[w];
					long long hh=(2ll<<t)-c[u]-c[v];
					b[u]+=(1ll<<t)-c[u];b[v]+=(1ll<<t)-c[v];
					int ff=0;
					for(int tt=t-1;tt>=0;--tt){
						int gs=0;
						for(int i=1;i<=n;++i)if(b[i]>>tt&1)++gs;
						if(gs%2==0)continue;
						if(gs==n){
							ff=1;break;
						}
						long long T=(1ll<<(tt+1))-1;
						long long mx=-1;int wz=0;
						for(int i=1;i<=n;++i){
							if((b[i]&T)>=(1ll<<tt))continue;
							if(mx<(b[i]&T))mx=(b[i]&T),wz=i;
						}
						hh+=(1ll<<tt)-mx;b[wz]+=(1ll<<tt)-mx;
					}
					if(!ff)ans=min(ans,hh);
				}
			}
		}
		ann=ans;printf("%lld\n",ans);
	}
}
namespace baoli{
	long long aj[100005];
	int p2[100005];
	int tt;vector<pair<int,long long>>vv[20005];
	long long aa[65][100005];
	int hh[65],pp[65][100005];
	int tj[100005],st[105],sl=0;
	bool dfs(int t,long long he){
		if(t<0){
			if(he>ann)return 0;
			--m;
			vector<pair<int,long long>>vc;
			for(int i=1;i<=sl;++i){
				int x=st[i];
				if(aj[x])vc.emplace_back(x,aj[x]);
			}
			sort(vc.begin(),vc.end());
			vv[++tt]=vc;
			return 1;
		}
		int gs=hh[t];
		for(int i=1;i<=sl;++i){
			int j=st[i];
			gs-=aa[t][j]>>t&1;
		}
		if(gs%2==0)return dfs(t-1,he);
		if(gs==n)return 0;
		int fl=0,cg=1;
		for(int i=n-gs;i>=1&&cg&&m;--i){
			int j=pp[t][i];
			if(tj[j])continue;
			if((aa[t][j]>>t&1))continue;
			long long sb=(1ll<<t)-aa[t][j];
			aj[j]+=sb;++tj[j];
			if(tj[j]==1)st[++sl]=j;
			int ff=1;
			if(dfs(t-1,he+sb))fl=1;
			else ff=0;
			if(tj[j]==1)--sl;
			--tj[j];aj[j]-=sb;
			if(!ff)return fl;
		}
		for(int i=1;i<=sl&&cg&&m;++i){
			int j=st[i];
			long long sb=(1ll<<t)-0;
			aj[j]+=sb;++tj[j];
			if(tj[j]==1)st[++sl]=j;
			int ff=1;
			if(dfs(t-1,he+sb))fl=1;
			else ff=0;
			if(tj[j]==1)--sl;
			--tj[j];aj[j]-=sb;
			if(!ff)return fl;
		}
		return fl;
	}
	void solve(){
		for(int i=1;i<=n;++i)p2[i]=i;
		sort(p2+1,p2+n+1,[&](int x,int y){
			return a[x]<a[y];
		});
		for(int t=60;t>=0;--t){
			hh[t]=0;
			int w=0;
			for(int i=1;i<=n;++i){
				aa[t][i]=a[i]&((1ll<<(t+1))-1);
				pp[t][i]=p2[i];hh[t]+=(aa[t][i]>>t&1);
			}
			for(int i=1;i<=n;++i){
				if(aa[t][p2[i]]<(1ll<<t))w=i;
			}
			inplace_merge(p2+1,p2+w+1,p2+n+1,[&](int x,int y){
				return (a[x]&((1ll<<t)-1))<(a[y]&((1ll<<t)-1));
			});
		}
		for(int i=1;i<=n;++i)aj[i]=0;
		tt=0;dfs(59,0);
	}
	void solve2(){
		for(int t=60;t>=1;--t){
			int gs=0;
			for(int j=1;j<=n;++j)gs+=(a[j]>>t&1);
			if(gs%2)break;
			int w=0;
			for(int j=n;j>=1;--j){
				if(aa[t][pp[t][j]]>=(1ll<<t))continue;
				w=j;break;
			}
			for(int j=w;j>=2;--j){
				int ff=0;
				for(int k=j-1;k>=1;--k){
					int x=pp[t][j],y=pp[t][k];
					st[++sl]=x;st[++sl]=y;
					++tj[x];++tj[y];
					aj[x]+=(1ll<<t)-aa[t][x];
					aj[y]+=(1ll<<t)-aa[t][y];
					if(!dfs(t-1,(2ll<<t)-aa[t][x]-aa[t][y])){
						--tj[x];--tj[y];--sl;--sl;
						aj[x]-=(1ll<<t)-aa[t][x];
						aj[y]-=(1ll<<t)-aa[t][y];
						break;
					}
					--tj[x];--tj[y];--sl;--sl;++ff;
					aj[x]-=(1ll<<t)-aa[t][x];
					aj[y]-=(1ll<<t)-aa[t][y];
				}
				if(!ff)break;
			}
		}
	}
	void output(){
		printf("%d\n",tt);
tt=0;
		for(int i=1;i<=tt;++i){
			vector<pair<int,long long>>vc=vv[i];
			sort(vc.begin(),vc.end());
			int z=vc.size();
			printf("%d\n",z);
			for(int j=0;j<z;++j)printf("%d ",vc[j].first);
			printf("\n");
			for(int j=0;j<z;++j)printf("%lld ",vc[j].second);
			printf("\n");
		}
	}
}
int main(){
	int c=read(),T=read();
	assert(c>=0);
	while(T--){
		n=read(),m=read();
		for(int i=1;i<=n;++i)a[i]=readl();
		yuchu::solve();
		baoli::solve();
		if(n%2)baoli::solve2();
		baoli::output();
	}
	return 0;
}