human
Can you solve the below in PYTHON3?
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 

What is a Python code to find such a permutation p for which the surprise value of the results is maximum possible?
assistant
#Here is Python code to find such a permutation p for which the surprise value of the results is maximum possible.

''' E. Math Test
https://codeforces.com/contest/1622/problem/E
'''

import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline  # decode().strip() if str
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(r"\((.*)\)", 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')

# -----------------------------------------

# let mask[i] = 1 if r[i] >= x[i] (score better than expected), 0 if r[i] < x[i]
# then total surprise = SUM_{i: mask[i]==0} (x[i] - r[i]) + SUM_{i: mask[i]==1} (r[i] - x[i])
# a question with score v will contribute: v * (num students with mask 1 who solved - num students with mask 0 who solved)

def solve(N, M, X, A):
    def bucketsort(order, seq):
        mn = min(seq)
        seq = [x - mn for x in seq]
        buckets = [0] * (max(seq) + 1)
        
        for x in seq:
            buckets[x] += 1
        for i in range(len(buckets) - 1):
            buckets[i + 1] += buckets[i]

        new_order = [-1] * len(seq)
        for i in reversed(order):
            x = seq[i]
            idx = buckets[x] = buckets[x] - 1
            new_order[idx] = i

        return new_order
        
    mxk, mxv = -INF, []
    for mask in range(1 << N):
        x = 0

        # delta[q] = num students with mask 1 who solved q - num students with mask 0 who solved q
        delta = [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):
                delta[q] += A[i][q] * sign

        # greedily assign highest score to q with highest delta
        order = bucketsort(list(range(M)),...