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.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.math.*;

/**
 __                  __
 ( _)                ( _)
 / / \\              / /\_\_
 / /   \\            / / | \ \
 / /     \\          / /  |\ \ \
 /  /   ,  \ ,       / /   /|  \ \
 /  /    |\_ /|      / /   / \   \_\
 /  /  |\/ _ '_| \   / /   /   \    \\
 |  /   |/  0 \0\    / |    |    \    \\
 |    |\|      \_\_ /  /    |     \    \\
 |  | |/    \.\ o\o)  /      \     |    \\
 \    |     /\\`v-v  /        |    |     \\
 | \/    /_| \\_|  /         |    | \    \\
 | |    /__/_ `-` /   _____  |    |  \    \\
 \|    [__]  \_/  |_________  \   |   \    ()
 /    [___] (    \         \  |\ |   |   //
 |    [___]                  |\| \|   /  |/
 /|    [____]                  \  |/\ / / ||
 (  \   [____ /     ) _\      \  \    \| | ||
 \  \  [_____|    / /     __/    \   / / //
 |   \ [_____/   / /        \    |   \/ //
 |   /  '----|   /=\____   _/    |   / //
 __ /  /        |  /   ___/  _/\    \  | ||
 (/-(/-\)       /   \  (/\/\)/  |    /  | /
 (/\/\)           /   /   //
 _________/   /    /
 \____________/    (


 @author NTUDragons-Reborn
 */

public class Solution{
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }
    // main solver
    static class Task{

        double eps= 0.00000001;
        static final int MAXN = 10015;
        static final int MOD= 998244353;

        // stores smallest prime factor for every number
        static int spf[] = new int[MAXN];

        static boolean[] prime;

        Map<Integer,Set<Integer>> dp= new HashMap<>();

        // Calculating SPF (Smallest Prime Factor) for every
        // number till MAXN.
        // Time Complexity : O(nloglogn)
        public void sieve()
        {
            spf[1] = 1;
            for (int i=2; i<MAXN; i++)

                // marking smallest prime factor for every
                // number to be itself.
                spf[i] = i;

            // separately marking spf for every even
            // number as 2
            for (int i=4; i<MAXN; i+=2)
                spf[i] = 2;

            for (int i=3; i*i<MAXN; i++)
            {
                // checking if i is prime
                if (spf[i] == i)
                {
                    // marking SPF for all numbers divisible by i
                    for (int j=i*i; j<MAXN; j+=i)

                        // marking spf[j] if it is not
                        // previously marked
                        if (spf[j]==j)
                            spf[j] = i;
                }
            }
        }

        void sieveOfEratosthenes(int n)
        {
            // Create a boolean array
            // "prime[0..n]" and
            // initialize all entries
            // it as true. A value in
            // prime[i] will finally be
            // false if i is Not a
            // prime, else true.
            prime= new boolean[n + 1];
            for (int i = 0; i <= n; i++)
                prime[i] = true;
    
            for (int p = 2; p * p <= n; p++)
            {
                // If prime[p] is not changed, then it is a
                // prime
                if (prime[p] == true)
                {
                    // Update all multiples of p
                    for (int i = p * p; i <= n; i += p)
                        prime[i] = false;
                }
            }
        }

        // A O(log n) function returning primefactorization
        // by dividing by smallest prime factor at every step
        public Set<Integer> getFactorization(int x)
        {
            if(dp.containsKey(x)) return dp.get(x);
            Set<Integer> ret = new HashSet<>();
            while (x != 1)
            {
                if(spf[x]!=2) ret.add(spf[x]);
                x = x / spf[x];
            }
            dp.put(x,ret);
            return ret;
        }
        // function to find first index >= x
        public int lowerIndex(List<Integer> arr, int n, int x)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr.get(mid) >= x)
                    h = mid - 1;
                else
                    l = mid + 1;
            }
            return l;
        }
        public int lowerIndex(int[] arr, int n, int x)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr[mid] >= x)
                    h = mid - 1;
                else
                    l = mid + 1;
            }
            return l;
        }

        // function to find last index <= y
        public int upperIndex(List<Integer> arr, int n, int y)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr.get(mid) <= y)
                    l = mid + 1;
                else
                    h = mid - 1;
            }
            return h;
        }
        public int upperIndex(int[] arr, int n, int y)
        {
            int l = 0, h = n - 1;
            while (l <= h)
            {
                int mid = (l + h) / 2;
                if (arr[mid] <= y)
                    l = mid + 1;
                else
                    h = mid - 1;
            }
            return h;
        }

        // function to count elements within given range
        public int countInRange(List<Integer> arr, int n, int x, int y)
        {
            // initialize result
            int count = 0;
            count = upperIndex(arr, n, y) -
                    lowerIndex(arr, n, x) + 1;
            return count;
        }

        public int add(int a, int b){
            a+=b;
            while(a>=MOD) a-=MOD;
            while(a<0) a+=MOD;
            return a;
        }

        public int mul(int a, int b){
            long res= (long)a*(long)b;
            return (int)(res%MOD);
        }

        public int power(int a, int b) {
            int ans=1;
            while(b>0){
                if((b&1)!=0) ans= mul(ans,a);
                b>>=1;
                a= mul(a,a);
            }
            return ans;
        }

        int[] fact= new int[MAXN];
        int[] inv= new int[MAXN];

        public int Ckn(int n, int k){
            if(k<0 || n<0) return 0;
            if(n<k) return 0;
            return mul(mul(fact[n],inv[k]),inv[n-k]);
        }

        public int inverse(int a){
            return power(a,MOD-2);
        }

        public void preprocess() {
            fact[0]=1;
            for(int i=1;i<MAXN;i++) fact[i]= mul(fact[i-1],i);
            inv[MAXN-1]= inverse(fact[MAXN-1]);
            for(int i=MAXN-2;i>=0;i--){
                inv[i]= mul(inv[i+1],i+1);
            }
        }

        /**
         * return VALUE of lower bound for unsorted array
         */
        public int lowerBoundNormalArray(int[] arr, int x){
            TreeSet<Integer> set= new TreeSet<>();
            for(int num: arr) set.add(num);
            return set.lower(x);
        }
        /**
         * return VALUE of upper bound for unsorted array
         */
        public int upperBoundNormalArray(int[] arr, int x){
            TreeSet<Integer> set= new TreeSet<>();
            for(int num: arr) set.add(num);
            return set.higher(x);
        }

        public void debugArr(int[] arr){
            for(int i: arr) out.print(i+" ");
            out.println();
        }

        public int rand(){
            int min=0, max= MAXN;
            int random_int = (int)Math.floor(Math.random()*(max-min+1)+min);
            return random_int;
        }
        
        public void suffleSort(int[] arr){
            shuffleArray(arr);
            Arrays.sort(arr);
        }


        public void shuffleArray(int[] ar)
        {
            // If running on Java 6 or older, use `new Random()` on RHS here
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--)
            {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            int a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
            }
        }
        
        InputReader in; PrintWriter out;
        Scanner sc= new Scanner(System.in);
        CustomFileReader cin;
        int[] xor= new int[3*100000+5];
        int[] pow2= new int[1000000+1];
        public void solve(InputReader in, PrintWriter out) {
            this.in=in; this.out=out;
            // sieve();
            // pow2[0]=1;
            // for(int i=1;i<pow2.length;i++){
            //     pow2[i]= mul(pow2[i-1],2);
            // }
            int t=in.nextInt();
            // preprocess();
            // int t=in.nextInt();
            // int t= cin.nextIntArrLine()[0];
            for(int i=1;i<=t;i++) solveE(i);
        }
    
        final double pi= Math.acos(-1);
        static Point base;

        void hack(int t){
            for(int n=1;n<=1000000000;n++){
                if(test3(n)!=test2(n)) System.out.println(n);
            }
        }
        int test1(int n){
            return (int)Math.sqrt(n) + (int)Math.cbrt(n) - (int)Math.pow(n, (double)1.0/6);
        }
        int test2(int n){
            int temp = (int)Math.cbrt(n);
            return (int)Math.sqrt(n) + temp - (int)(Math.sqrt(temp));
        }
        int test3(int n) {
            Set<Integer> res= new HashSet<>();
            for(int i=1;i*i<=n;i++) res.add(i*i);
            for(int i=1;i*i*i<=n;i++) res.add(i*i*i);
            return res.size();
        }
        void solveA(int t) {
            String s= in.nextToken();
            if (s.length() % 2 == 1) {
                out.println("NO");
                return;
            }
            int m = s.length() / 2;
            boolean ok = (s.substring(0, m).equals(s.substring(m,s.length())));
            if(ok) out.println("YES");
            else out.println("NO");
        }
         
        void solveB(int t) {
            int n= in.nextInt();
            int temp = (int)Math.cbrt(n);
            out.println((int)Math.sqrt(n) + temp - (int)(Math.sqrt(temp)));
        }

        void solveC(int t){
            char[] a= in.nextToken().toCharArray(), s= in.nextToken().toCharArray();
            int i= s.length-1;
            String b="";
            for(int j=a.length-1;j>=0;j--){
                if(i<0){out.println(-1); return;}
                if(s[i]>=a[j]) b= ""+(s[i]-a[j])+b;
                else{
                    i--;
                    if(i<0 || i+1>=s.length) {out.println(-1); return;}
                    int num= Integer.parseInt(""+s[i]+s[i+1]);
                    int num2= Integer.parseInt(""+a[j]);
                    if(num-num2>9 || num-num2<0){out.println(-1); return;}
                    b= ""+(num-num2)+b;
                    // System.out.println(b);
                }
                i--;
            }
            while(i>=0) {
                b= ""+s[i]+b;
                i--;
            }
            if(b.length()==0) out.println(-1);
            else {
                out.println(Long.parseLong(b));
            }
        }

        char[]s;
        int[] pre;
        int n,k;
        List<Integer> idx;
        void solveD(int t) {
           n= in.nextInt(); k= in.nextInt();
           char[] s= in.nextToken().toCharArray();
           pre= new int[n+1];
           idx= new ArrayList<>();
           for(int i=0;i<n;i++){
               pre[i+1]= pre[i];
               if(s[i]=='1') {
                pre[i+1]++;
                idx.add(i);
               }
           }
           if(k<=0 || k>pre[n]){out.println(1); return;}
           int i=0;
           int  res=0;
           for(;i+k-1<idx.size();i++){
                int l=-1, r=-1;
                if(i==0) l=0;
                else l= idx.get(i-1)+1;
                if(i+k>=idx.size()) r= n-1;
                else r= idx.get(i+k)-1;
                int num1= pre[r+1]-pre[l];
                int tot = r-l+1;
                int num0= tot-num1;
                res= add(res, calc(l,r));
                if(i>0) res= add(res, -calc(idx.get(i-1)+1,idx.get(i+k-1)-1));
           }

           out.println(res);
        }

        int calc(int l, int r){
            int num0=0,num1=0;
            try{
                num1= pre[r+1]-pre[l];
            int tot = r-l+1;
            num0= tot-num1;
            return mul(mul(fact[tot],inv[num1]), inv[num0]);
            }
            catch(Exception e){
                out.println(l+" "+r+" "+num1+" "+num0);
            }
            return -1;
        }

        void solveE(int t){
            int n= in.nextInt(), m= in.nextInt();
            int[] x= in.nextIntArr(n);
            char[][] p= new char[n][m];
            for(int i=0;i<n;i++){
                String temp= in.nextToken();
                for(int j=0;j<m;j++){
                    p[i][j]= temp.charAt(j);
                }
            }

            int[] w= new int[m];
            List<Pair> a= new ArrayList<>();
            for(int i=0;i<n;i++){
                a.add(new Pair(x[i],i));
            }
            Collections.sort(a);
            double half= (double)m*(m+1)/4;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(p[a.get(i).y][j]=='1') {
                        if(a.get(i).x>half) w[j]--;
                        else w[j]++;
                    }
                    else{
                        if(a.get(i).x>half) w[j]++;
                        else w[j]--;
                    }
                }
                
            }
            List<Pair> ques= new ArrayList<>();
            for(int i=0;i<m;i++) ques.add(new Pair(w[i],i));
            Collections.sort(ques);
            int[] res= new int[m];
            int weight=1;
            for(int i=0;i<ques.size();i++){
                res[ques.get(i).y]= weight++;
            }
            for(int i: res) out.print(i+" ");
            out.println();
        }
            
    
        static class ListNode{
            int idx=-1;
            ListNode next= null;
            public ListNode(int idx){
                this.idx= idx;
            }
        }
        

        static class Node implements Comparable<Node>{
            char op;
            int s;
            public Node (char op, int s) {
                this.op= op;
                this.s= s;
            }
            @Override
            public int compareTo(Node o) {
                if (this.s==o.s) return (int)(this.op-o.op);
                return this.s-o.s;
            }

        }

        private long distance(Point p1, Point p2) {
            long x= p1.x-p2.x, y= p1.y-p2.y;
            return x*x+y*y;
        }


        private boolean eqPoint(Point p1, Point p2){
            return p1.x==p2.x && p1.y==p2.y;
        }

        private double polarAngle(Point p1, Point p2) {
            // p1 -> p2
            if (p1.x==p2.x) return pi/2;
            else if (p1.y==p2.y){
                if(p1.x<p2.x) return 0;
                else return pi;
            }
            else {
                double y= (double)p2.y-(double)p1.y;
                double x= (double)p2.x-(double)p1.x;
                BigDecimal alpha1= new BigDecimal(y);
                BigDecimal alpha2= new BigDecimal(x);
                BigDecimal val= alpha1.divide(alpha2);

                double angle= Math.atan(val.doubleValue());
                if (angle<0) angle+= pi;
                out.println("angle: "+angle);
                return angle;
            }
        }

        private boolean isRightTurn(Point p1, Point p2, Point p3){
            Vector v1= new Vector(p1,p2), v2= new Vector(p1,p3);
            if(crossProd(v1,v2)<0) return true;
            else return false;
        }

        private long crossProd(Vector v1, Vector v2){
            //x1*y2-x2*y1
            return v1.x*v2.y - v2.x*v1.y;
        }

        static class PointAngle implements Comparable<PointAngle>{
            Point p;
            double angle;
            long dis;
            public PointAngle(Point p, double angle, long dis) {
                this.p= p;
                this.angle= angle;
                this.dis= dis;

            }

            @Override
            public int compareTo(PointAngle o) {
                double dif= this.angle-o.angle;
                if (dif <0) return -1;
                else if(dif >0) return 1;
                else {
                    long dif2r= this.dis-o.dis;
                    long dif2l= o.dis-this.dis;

                    if (base.x < this.p.x) return intDif(dif2r);
                    else return intDif(dif2l); 
                    
                }
            }

            private int intDif(long a){
                if (a>0) return 1;
                else if(a<0) return -1;
                else return 0;
            }
        }


    
        
        public long _gcd(long a,  long b)
        {

            if(b == 0) {
                return a;
            }
            else {
                return _gcd(b, a % b);
            }
        }
        public long _lcm(long a, long b){
            return (a*b)/_gcd(a,b);
        }

    }


    // static class SEG {

    //     Pair[] segtree;
        
    //     public SEG(int n){
            
    //         segtree= new Pair[4*n];
    //         Arrays.fill(segtree, new Pair(-1,Long.MAX_VALUE));
    //     }
    //     // void buildTree(int l, int r, int index) {
    //     //     if (l == r) {
    //     //         segtree[index].y = a[l];
    //     //         return;
    //     //     }
    //     //     int mid = (l + r) / 2;
    //     //     buildTree(l, mid, 2 * index + 1);
    //     //     buildTree(mid + 1, r, 2 * index + 2);
    //     //     segtree[index].y = Math.min(segtree[2 * index + 1].y, segtree[2 * index + 2].y);
    //     // }
        
    //     void update(int l, int r, int index, int pos, Pair val) {
    //         if (l == r) {
    //             segtree[index] = val;
    //             return;
    //         }
    //         int mid = (l + r) / 2;
    //         if (pos <= mid) update(l, mid, 2 * index + 1, pos, val);
    //         else update(mid + 1, r, 2 * index + 2, pos, val);
    //         if(segtree[2 * index + 1].y < segtree[2 * index + 2].y){
    //             segtree[index]= segtree[2 * index + 1];
    //         }
    //         else {
    //             segtree[index]= segtree[2 * index + 2];
    //         }
    //     }
        
    //     // Pair query(int l, int r, int from, int to, int index) {
    //     //     if (from <= l && r <= to)
    //     //         return segtree[index];
    //     //     if (r < from | to < l)
    //     //         return 0;
    //     //     int mid = (l + r) / 2;
    //     //     Pair left= query(l, mid, from, to, 2 * index + 1);
    //     //     Pair right= query(mid + 1, r, from, to, 2 * index + 2);
    //     //     if(left.y < right.y) return left;
    //     //     else return right;
            
    //     // }
        
        
    // }

    static class Venice{
        public Map<Long,Long> m= new HashMap<>();
        public long base=0;
        public long totalValue=0;
        private int M= 1000000007;

        private long addMod(long a, long b){
            a+=b;
            if(a>=M) a-=M;
            return a;
        }

        public void reset(){
            m= new HashMap<>();
            base=0;
            totalValue=0;
        }
        public void update(long add){
            base= base+ add;
        }
        public void add(long key, long val){
            long newKey= key-base;
            m.put(newKey, addMod(m.getOrDefault(newKey,(long)0),val));
        }
    }



    static class Tuple implements Comparable<Tuple>{
        int x, y, z;
        public Tuple(int x, int y, int z){
            this.x= x;
            this.y= y;
            this.z=z;
        }
        @Override
        public int compareTo(Tuple o){
            return this.z-o.z;
        }
    }

    static class Point implements Comparable<Point>{
        public long x;
        public long y;
        public Point(long x, long y){
            this.x= x;
            this.y= y;
        }

        @Override
        public int compareTo(Point o) {
            if(this.y!=o.y) return (int)(this.y-o.y);
            return (int)(this.x-o.x);
        }
    }

    static class Vector {
        public long x;
        public long y;

        // p1 -> p2
        public Vector(Point p1, Point p2){
            this.x= p2.x-p1.x;
            this.y= p2.y-p1.y;
        }
    }

    static class Pair implements Comparable<Pair>{
        public int x;
        public int y;
        public Pair(int x, int y){
            this.x= x;
            this.y= y;
        }

        @Override
        public int compareTo(Pair o) {
            if(this.x!=o.x) return this.x-o.x;
            return (int)(this.y-o.y);
        }
    }

    // public static class compareL implements Comparator<Tuple>{
    //     @Override
    //     public int compare(Tuple t1, Tuple t2) {
    //         return t2.l - t1.l;
    //     }
    // }

    // fast input reader class;
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        public double nextDouble(){
            return Double.parseDouble(nextToken());
        }
        public long nextLong(){
            return Long.parseLong(nextToken());
        }
        public int[] nextIntArr(int n){
            int[] arr= new int[n];
            for(int i=0;i<n;i++) arr[i]= nextInt();
            return arr;
        }
        public long[] nextLongArr(int n){
            long[] arr= new long[n];
            for(int i=0;i<n;i++) arr[i]= nextLong();
            return arr;
        }
        public List<Integer> nextIntList(int n){
            List<Integer> arr= new ArrayList<>();
            for(int i=0;i<n;i++) arr.add(nextInt());
            return arr;
        }
        public int[][] nextIntMatArr(int n, int m){
            int[][] mat= new int[n][m];
            for(int i=0;i<n;i++) for(int j=0;j<m;j++) mat[i][j]= nextInt();
            return mat;
        }
        public List<List<Integer>> nextIntMatList(int n, int m){
            List<List<Integer>> mat= new ArrayList<>();
            for(int i=0;i<n;i++){
                List<Integer> temp= new ArrayList<>();
                for(int j=0;j<m;j++) temp.add(nextInt());
                mat.add(temp);
            }
            return mat;
        }
        public char[] nextStringCharArr(){
            return nextToken().toCharArray();
        }
    }

    static class CustomFileReader{
        String path="";
        Scanner sc;
        public CustomFileReader(String path){
            this.path=path;
            try{
                sc= new Scanner(new File(path));
            }
            catch(Exception e){}
        }
        public String nextLine(){
            return sc.nextLine();
        }
        public int[] nextIntArrLine(){
            String line= sc.nextLine();
            String[] part= line.split("[\\s+]");
            int[] res= new int[part.length];
            for(int i=0;i<res.length;i++) res[i]= Integer.parseInt(part[i]);
            return res;
        }
    }
}