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.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Solution {
    // VM options: -Xmx1024m -Xss1024m


    private void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        int[] x = nextIntArray(n);
        char[][] s = new char[n][];
        for (int i = 0; i < n; i++) {
            s[i] = nextToken().toCharArray();
        }
        Int[] idx = new Int[m];
        for (int i = 0; i < m; i++) idx[i] = new Int(i);
        long res = -1;
        int[] rres = new int[0];
        for (int mask = 0; mask < (1 << n); mask++) {
            int[] priority = new int[m];
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < m; j++) {
                        if (s[i][j] == '1') {
                            priority[j]++;
                        }
                    }
                } else {
                    for (int j = 0; j < m; j++) {
                        if (s[i][j] == '1') {
                            priority[j]--;
                        }
                    }
                }
            }
            Arrays.sort(idx, new Comparator<Int>() {
                @Override
                public int compare(Int o1, Int o2) {
                    return priority[o1.x] - priority[o2.x];
                }
            });
            int[] r = new int[m];
            for (int i = 0; i < m; i++) {
                r[idx[i].x] = i + 1;
            }
            long tres = 0;
            for (int i = 0; i < n; i++) {
                long tt = 0;
                for (int j = 0; j < m; j++) {
                    if (s[i][j] == '1') {
                        tt += r[j];
                    }
                }
                tres += Math.abs(tt - x[i]);
            }
            if (tres > res) {
                res = tres;
                rres = r;
            }
        }
        for (int i = 0; i < m; i++) {
            out.print(rres[i] + " ");
        }
        out.println();
    }

    private static class Int {
        int x;

        public Int(int x) {
            this.x = x;
        }
    }

    private static final String inputFilename = "input.txt";
    private static final String outputFilename = "output.txt";
    private BufferedReader in;
    private StringTokenizer line;
    private PrintWriter out;
    private final boolean isDebug;

    private Solution(boolean isDebug) {
        this.isDebug = isDebug;
    }

    public static void main(String[] args) throws IOException {
        new Solution(Arrays.asList(args).contains("DEBUG_MODE")).run(args);
    }

    private void run(String[] args) throws IOException {
        if (isDebug) {
            in = new BufferedReader(new InputStreamReader(new FileInputStream(inputFilename)));
//            in = new BufferedReader(new InputStreamReader(System.in));
        } else {
            in = new BufferedReader(new InputStreamReader(System.in));
        }
        out = new PrintWriter(System.out);
//        out = new PrintWriter(outputFilename);


//        int t = isDebug ? nextInt() : 1;
//        int t = 1;

        int t = nextInt();
        for (int i = 0; i < t; i++) {
//            out.print("Case #" + (i + 1) + ": ");
            solve();
            out.flush();
        }

        in.close();
        out.flush();
        out.close();
    }

    private void println(Object... objects) {
        boolean isFirst = true;
        for (Object o : objects) {
            if (!isFirst) {
                out.print(" ");
            } else {
                isFirst = false;
            }
            out.print(o.toString());
        }
        out.println();
    }

    private int[] nextIntArray(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = nextInt();
        }
        return res;
    }

    private long[] nextLongArray(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    private String nextToken() throws IOException {
        while (line == null || !line.hasMoreTokens()) {
            line = new StringTokenizer(in.readLine());
        }
        return line.nextToken();
    }

    private static void assertPredicate(boolean p) {
        if (!p) {
            throw new RuntimeException();
        }
    }

    private static void assertPredicate(boolean p, String message) {
        if (!p) {
            throw new RuntimeException(message);
        }
    }

    private static void assertNotEqual(int unexpected, int actual) {
        if (actual == unexpected) {
            throw new RuntimeException("assertNotEqual: " + unexpected + " == " + actual);
        }
    }

    private static void assertEqual(int expected, int actual) {
        if (expected != actual) {
            throw new RuntimeException("assertEqual: " + expected + " != " + actual);
        }
    }
}
