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

Difficulty: HARD
Tags: Complete search

Bit manipulation

Greedy algorithms
Skill types: Complete search

Bit manipulation

Greedy algorithms

Starter code:

Solutions:
I = lambda : [*map(int, input().split())]
r = range
s = sum
for _ in [0] * I()[0]:
	(n, m) = I()
	e = I()
	M = [[*map(int, [*input().strip()])] for i in r(n)]
	o = [bin(i).count('1') for i in r(1 << n)]
	q = [s((1 << i for i in r(n) if M[i][j])) for j in r(m)]
	b = -1
	for i in r(1 << n):
		c = [0] * (n + 1)
		v = [0] * m
		d = c[:]
		P = v[:]
		for j in r(m):
			v[j] = o[i ^ q[j]]
			c[v[j]] += 1
		for j in r(n):
			d[j + 1] = d[j] + c[j]
		for j in r(m):
			d[v[j]] += 1
			P[j] = d[v[j]]
		T = 2 * s((e[j] for j in r(n) if i >> j & 1)) - s(e) + s(((o[q[j]] - 2 * o[i & q[j]]) * P[j] for j in r(m)))
		if T > b:
			(b, p) = (T, P)
	print(*p)


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') is not None
if DEBUG:
	from inspect import currentframe, getframeinfo
	from re import search

def debug(*args):
	if not DEBUG:
		return
	frame = currentframe().f_back
	s = getframeinfo(frame).code_context[0]
	r = search('\\((.*)\\)', s).group(1)
	vnames = r.split(', ')
	var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
	prefix = f'{currentframe().f_back.f_lineno:02d}: '
	print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

def bucket_sort(vals, order=None):
	N = len(vals)
	if order is None:
		order = list(range(N))
	mn = min(vals)
	vals = [v - mn for v in vals]
	mx = max(vals)
	count = [0] * (mx + 1)
	for v in vals:
		count[v] += 1
	for i in range(len(count) - 1):
		count[i + 1] += count[i]
	new_order = [0] * N
	for i in reversed(order):
		v = vals[i]
		c = count[v]
		new_order[c - 1] = i
		count[v] -= 1
	return new_order

def solve(N, M, X, A):
	(mx, mxv) = (-INF, [])
	for mask in range(1 << N):
		x = 0
		add = [0] * M
		for i in range(N):
			sign = 1 if mask >> i & 1 == 1 else -1
			x -= sign * X[i]
			for q in range(M):
				add[q] += A[i][q] * sign
		order = bucket_sort(add)
		x += sum(((v + 1) * add[q] for (v, q) in enumerate(order)))
		if x > mx:
			(mx, mxv) = (x, order)
	res = [-1] * M
	for (v, q) in enumerate(mxv):
		res[q] = v + 1
	return res

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = list(map(int, input().split()))
		X = list(map(int, input().split()))
		A = [list(map(int, list(input().decode().strip()))) for _ in range(N)]
		out = solve(N, M, X, A)
		print(*out)
main()


import sys
import time
import random
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
	(n, m) = I()
	expect = I()
	mat = []
	for i in range(n):
		mat.append([*map(int, [*sys.stdin.readline().strip()])])
	onebits = []
	for i in range(1 << n):
		onebits.append(bin(i).count('1'))
	qrep = [0] * m
	for i in range(n):
		for j in range(m):
			if mat[i][j]:
				qrep[j] += 1 << i
	big = -1
	perm = None
	for i in range(1 << n):
		count = [0] * (n + 1)
		vals = [0] * m
		for j in range(m):
			x = onebits[i ^ qrep[j]]
			vals[j] = x
			count[x] += 1
		ind = [0] * (n + 1)
		for j in range(n):
			ind[j + 1] = ind[j] + count[j]
		qvals = [0] * m
		for j in range(m):
			ind[vals[j]] += 1
			qvals[j] = ind[vals[j]]
		tot = 0
		for j in range(n):
			if i >> j & 1:
				tot += expect[j]
			else:
				tot -= expect[j]
		for j in range(m):
			right = onebits[qrep[j]]
			x = onebits[i & qrep[j]]
			tot += (right - 2 * x) * qvals[j]
		if tot > big:
			big = tot
			perm = qvals
	print(*perm)