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 java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static int MOD = 1000000007;

    // After writing solution, quick scan for:
    //   array out of bounds
    //   special cases e.g. n=1?
    //   npe, particularly in maps
    //
    // Big numbers arithmetic bugs:
    //   int overflow
    //   sorting, or taking max, after MOD
    void solve() throws IOException {
        int T = ri();
        for (int Ti = 0; Ti < T; Ti++) {
            int[] nm = ril(2);
            int n = nm[0];  // tiny
            int m = nm[1];
            int[] x = ril(n);

            char[][] results = new char[n][];
            for (int i = 0; i < n; i++) results[i] = rs();

            // Find a permutation of the m=10^4 questions.
            // There are few students

            // We can't take any question individually, since we only think about the sum
            // of points for each student...

            // What about for an individual student?
            // Let's say his score was x[i]. We would be surprised if the sum of his points
            // was super low or super high...
            //
            // There is sacrifice: if we make i's score super high, then we may inadvertantly
            // make other students' scores not surprising at all.
            // We must link the students somehow. In a graph?

            // Connect two students with an edge j if they both do question j.
            // Multi edges are clearly allowed.

            // 2^10 = 1024. Can we brute force on which students should be low vs high?
            // 0 means low, 1 means high
            // Give the lowest scores to the problems that the "bad kids" solve.
            // Among them, the lowest score should be given to the problem that a lot of the
            // bad kids solve.

            long maxSurprise = -1;
            int[] bestAssignment = null;

            List<Integer> badorder = new ArrayList<>(m);
            List<Integer> goodorder = new ArrayList<>(m);
            for (int i = 0; i < m; i++) {
                badorder.add(i);
                goodorder.add(i);
            }

            for (int mask = 0; mask < (1 << n); mask++) {
                int[] badkidsolves = new int[m];
                for (int i = 0; i < n; i++) {
                    if (((1 << i) & mask) > 0) continue;
                    for (int j = 0; j < m; j++) {
                        if (results[i][j] == '1') badkidsolves[j]++;
                    }
                }

                int[] goodkidsolves = new int[m];
                for (int i = 0; i < n; i++) {
                    if (((1 << i) & mask) == 0) continue;
                    for (int j = 0; j < m; j++) {
                        if (results[i][j] == '1') goodkidsolves[j]++;
                    }
                }

                Collections.sort(badorder, (i1, i2) -> -Integer.compare(badkidsolves[i1], badkidsolves[i2]));
                Collections.sort(goodorder, (i1, i2) -> -Integer.compare(goodkidsolves[i1], goodkidsolves[i2]));

                int[] assignment = new int[m];
                int lo = 1;
                int hi = m;
                for (int z : badorder) {
                    if (badkidsolves[z] == 0) break;
                    assignment[z] = lo++;
                }
                for (int z : goodorder) {
                    if (lo >= hi) break;
                    if (assignment[z] != 0) continue;
                    assignment[z] = hi--;
                }

                for (int j = 0; j < m && lo <= hi; j++) {
                    if (assignment[j] != 0) continue;
                    assignment[j] = lo++;
                }

                long surprise = 0;
                for (int i = 0; i < n; i++) {
                    long score = 0;
                    for (int j = 0; j < m; j++) if (results[i][j] == '1') score += assignment[j];
                    surprise += Math.abs(score - x[i]);
                }

                if (surprise > maxSurprise) {
                    maxSurprise = surprise;
                    bestAssignment = assignment;
                }
            }

            for (int z : bestAssignment) {
                pw.print(z + " ");
            }
            pw.println();
        }
    }
    // IMPORTANT
    // DID YOU CHECK THE COMMON MISTAKES ABOVE?

    // Template code below

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pw = new PrintWriter(System.out);

    public static void main(String[] args) throws IOException {
        Main m = new Main();
        m.solve();
        m.close();
    }

    void close() throws IOException {
        pw.flush();
        pw.close();
        br.close();
    }

    int ri() throws IOException {
        return Integer.parseInt(br.readLine().trim());
    }

    long rl() throws IOException {
        return Long.parseLong(br.readLine().trim());
    }

    int[] ril(int n) throws IOException {
        int[] nums = new int[n];
        int c = 0;
        for (int i = 0; i < n; i++) {
            int sign = 1;
            c = br.read();
            int x = 0;
            if (c == '-') {
                sign = -1;
                c = br.read();
            }
            while (c >= '0' && c <= '9') {
                x = x * 10 + c - '0';
                c = br.read();
            }
            nums[i] = x * sign;
        }
        while (c != '\n' && c != -1) c = br.read();
        return nums;
    }

    long[] rll(int n) throws IOException {
        long[] nums = new long[n];
        int c = 0;
        for (int i = 0; i < n; i++) {
            int sign = 1;
            c = br.read();
            long x = 0;
            if (c == '-') {
                sign = -1;
                c = br.read();
            }
            while (c >= '0' && c <= '9') {
                x = x * 10 + c - '0';
                c = br.read();
            }
            nums[i] = x * sign;
        }
        while (c != '\n' && c != -1) c = br.read();
        return nums;
    }

    int[] rkil() throws IOException {
        int sign = 1;
        int c = br.read();
        int x = 0;
        if (c == '-') {
            sign = -1;
            c = br.read();
        }
        while (c >= '0' && c <= '9') {
            x = x * 10 + c - '0';
            c = br.read();
        }
        return ril(x);
    }

    long[] rkll() throws IOException {
        int sign = 1;
        int c = br.read();
        int x = 0;
        if (c == '-') {
            sign = -1;
            c = br.read();
        }
        while (c >= '0' && c <= '9') {
            x = x * 10 + c - '0';
            c = br.read();
        }
        return rll(x);
    }

    char[] rs() throws IOException {
        return br.readLine().toCharArray();
    }

    void sort(int[] A) {
        Random r = new Random();
        for (int i = A.length-1; i > 0; i--) {
            int j = r.nextInt(i+1);
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
        Arrays.sort(A);
    }

    void printDouble(double d) {
        pw.printf("%.16f", d);
    }
}