Petya is a math teacher. n of his students has written a test consisting of m questions. For each student, it is known which questions he has answered correctly and which he has not.

If the student answers the j-th question correctly, he gets p_j points (otherwise, he gets 0 points). Moreover, the points for the questions are distributed in such a way that the array p is a permutation of numbers from 1 to m.

For the i-th student, Petya knows that he expects to get x_i points for the test. Petya wonders how unexpected the results could be. Petya believes that the surprise value of the results for students is equal to ∑_{i=1}^{n} |x_i - r_i|, where r_i is the number of points that the i-th student has got for the test.

Your task is to help Petya find such a permutation p for which the surprise value of the results is maximum possible. If there are multiple answers, print any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The first line of each test case contains two integers n and m (1 ≤ n ≤ 10; 1 ≤ m ≤ 10^4) — the number of students and the number of questions, respectively.

The second line contains n integers x_1, x_2, ..., x_n (0 ≤ x_i ≤ (m(m+1))/(2)), where x_i is the number of points that the i-th student expects to get.

This is followed by n lines, the i-th line contains the string s_i (|s_i| = m; s_{i, j} ∈ \{0, 1\}), where s_{i, j} is 1 if the i-th student has answered the j-th question correctly, and 0 otherwise.

The sum of m for all test cases does not exceed 10^4.

Output

For each test case, print m integers — a permutation p for which the surprise value of the results is maximum possible. If there are multiple answers, print any of them.

Example

Input


3
4 3
5 1 2 2
110
100
101
100
4 4
6 2 0 10
1001
0010
0110
0101
3 6
20 3 15
010110
000101
111111


Output


3 1 2 
2 3 4 1 
3 1 4 5 2 6 
#include<bits/stdc++.h>
#define File(s) freopen(#s".in","r",stdin),freopen(#s".out","w",stdout)
#ifdef GTRAKIOI
#define defrog(...) fprintf(stderr,__VA_ARGS__)
#else
#define defrog(...) 1
#endif
#if __cplusplus>=201703L
#define rg
#else
#define rg register
#endif
#define ri rg int
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int>pii;
typedef std::vector<int>vi;
typedef std::vector<pii>vpii;
typedef std::vector<vi >vvi;
typedef long double ld;
//typedef __int128 i128;
//typedef __uint128_t u128;
#define Tp template<typename T>
#define eb emplace_back

char ibuf[1<<15],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,1<<15,stdin),p1==p2)?EOF:*p1++)
struct FastIO{
	inline int rint(){rg char c,f=0;while((c=getchar())<48||c>57)f|=c=='-';ri unsigned a=c&15;while((c=getchar())>=48&&c<=57)a=a*10+(c&15);return f?~a+1:a;}
	inline ll rll(){rg char c,f=0;while((c=getchar())<48||c>57)f|=c=='-';rg ull a=c&15;while((c=getchar())>=48&&c<=57)a=a*10+(c&15);return f?~a+1:a;}
	inline operator int(){return rint();}
//	inline operator ll(){return rll();}
	/*inline void ou128(u128 x){
		u128 y=1;
		while(y<=x/10)y*=10;
		do putchar(x/y|48),x%=y,y/=10;while(y);
	}*/
	inline char rchar(){
		rg char c;
		while(!isgraph(c=getchar()));
		return c;
	}
}g90;

//const int M=1000000007,I2=500000004;
//inline int qpow(ll a,ll b){ri res=1;for(;b;a=a*a%M,b>>=1)if(b&1)res=res*a%M;return res;}
//#define pow qpow

std::mt19937 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rnd(const int&a,const int&b){
	return std::uniform_int_distribution<int>(a,b)(rng);
}
inline ld rnd(const ld&a,const ld&b){
	return std::uniform_real_distribution<ld>(a,b)(rng);
}
namespace MY_STD{
	Tp inline T abs(const T&a){return a<0?-a:a;}
}

const int N=10,SIZE=10101;
int x[N],s[N][SIZE];

signed main(){
	for(int T=g90;T--;){
		int n=g90,m=g90;
		for(int i=0;i<n;++i){
			x[i]=g90;
		}
		for(int i=0;i<n;++i){
			for(int j=0;j<m;++j)s[i][j]=g90.rchar()&15;
		}
		static int typ[N],typ_bak[N];
		ll ans=0;
		auto dfs=[&](auto&&self,int ly=0){
			if(ly>=n){
				static ll mul[SIZE];
				for(int j=0;j<=m;++j)mul[j]=0;
				for(int i=0;i<n;++i){
					if(typ[i])mul[m]-=x[i];
					else mul[m]+=x[i];
					for(int j=0;j<m;++j)if(s[i][j]){
						if(typ[i])mul[j]++;
						else mul[j]--;
					}
				}
				std::sort(mul,mul+m);
				ll res=0;
				for(int i=0;i<m;++i)res+=mul[i]*(i+1);
				res+=mul[m];
				if(res>ans){
					ans=res;
					memcpy(typ_bak,typ,sizeof(typ));
				}
				return;
			}
			typ[ly]=1;
			self(self,ly+1);
			typ[ly]=0;
			self(self,ly+1);
			return;
		};
		dfs(dfs,0);
		
		static ll mul[SIZE];
		for(int i=0;i<n;++i){
			if(typ_bak[i])mul[m]-=x[i];
			else mul[m]+=x[i];
			for(int j=0;j<m;++j)if(s[i][j]){
				if(typ_bak[i])mul[j]++;
				else mul[j]--;
			}
		}
		static int ord[SIZE];
		std::iota(ord,ord+m,0);
		std::sort(ord,ord+m,[](int i,int j){return mul[i]<mul[j];});
		for(int i=0;i<m;++i)printf("%d ",ord[i]+1);puts("");
	}
}