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 
import sys
infile = sys.stdin.buffer
def gs()  : return infile.readline().rstrip()
def gi()  : return int(gs())
def gss() : return gs().split()
def gis() : return [int(x) for x in gss()]
MOD = 998244353

def ee(e,j):
    return 1 if (e >> j) &1 else -1

def f(m,r,n):
    ans= -float('inf')
    m_ = len(m[0])    
    m = [list(map(int, list(row))) for row in m]
    res = [-1 for _ in range(m_)]
    t = [[-1,-1] for _ in range(m_)]

    for e in range(1 << n):

        cand = 0
        pm = -float('inf')
        for c in range(m_):
            p = 0
            for j in range(n): 
                p += ee(e,j) * m[j][c]
            t[c][0] = p
            t[c][1] = c
            pm = max(p, pm)

        for i in range(len(r)): cand -= ee(e,i) * r[i]
        
        if cand + (len(t) * pm) < ans: continue
        t.sort()
        for i in range(len(t)): cand += (i + 1) * t[i][0]
        if cand > ans:
            ans = cand
            for i in range(len(t)):
                res[t[i][1]] = i + 1
            
    return ' '.join(map(str,res))



def main(infn="") :
    global infile
    infile = open(infn,"r") if infn else open(sys.argv[1],"r") if len(sys.argv) > 1 else sys.stdin
    ###################################################################
        
    cs = gi()    
    for case in range(1, cs+1):
        n,m = gis()
        r = gis()
        print (f([gs() for i in range(n)],r,n))
    ###################################################################    
if __name__ == '__main__' : main()