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 
/*
stream Butter!
eggyHide eggyVengeance
I need U
xiao rerun when
 */
import static java.lang.Math.*;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1622E
{
    public static void main(String hi[]) throws Exception
    {
        int[] bc = new int[2000];
        for(int i=0; i < 2000; i++)
            bc[i] = Integer.bitCount(i);
        FastScanner infile = new FastScanner();
        int T = infile.nextInt();
        StringBuilder sb = new StringBuilder();
        while(T-->0)
        {
            int N = infile.nextInt();
            int M = infile.nextInt();
            int[] arr = infile.nextInts(N);
            int[][] grid = new int[N][M];
            for(int r=0; r < N; r++)
            {
                char[] line = infile.nextLine().toCharArray();
                for(int c=0; c < M; c++)
                    grid[r][c] = line[c]-'0';
            }
            int[] covers = new int[M];
            for(int i=0; i < M; i++)
                for(int b=0; b < N; b++)
                    covers[i] |= grid[b][i]*(1<<b);
            int[] res = new int[M];
            long best = -1;
            for(int mask=0; mask < 1<<N; mask++)
            {
                ArrayList<Unit> ls = new ArrayList<Unit>();
                for(int i=0; i < M; i++)
                {
                    int maximized = bc[mask&covers[i]];
                    int minimized = bc[covers[i]]-maximized;
                    ls.add(new Unit(i, maximized-minimized));
                }
                Collections.sort(ls);
                int[] values = new int[M];
                for(int i=0; i < M; i++)
                    values[ls.get(i).id] = i+1;
                long temp = 0L;
                for(int b=0; b < N; b++)
                {
                    if((mask&(1<<b)) > 0)
                        temp -= arr[b];
                    else
                        temp += arr[b];
                }
                for(int i=0; i < M; i++)
                {
                    Unit u = ls.get(i);
                    temp += values[u.id]*u.val;
                }
                if(best < temp)
                {
                    best = temp;
                    res = values;
                }
            }
            for(int x: res)
                sb.append(x+" ");
            sb.append("\n");
        }
        System.out.print(sb);
    }
}
class Unit implements Comparable<Unit>
{
    public int id;
    public int val;

    public Unit(int i, int v)
    {
        id = i;
        val = v;
    }
    public int compareTo(Unit oth)
    {
        return val-oth.val;
    }
}
class FastScanner
{
    //I don't understand how this works lmao
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    private char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }

    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }

    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}