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 
// package c1622;

import java.io.File;
import java.lang.invoke.MethodHandles;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

//
// Educational Codeforces Round 120 (Rated for Div. 2) 2021-12-27 06:35
// E. Math Test
// https://codeforces.com/contest/1622/problem/E
// time limit per test 2 seconds; memory limit per test 256 megabytes
// public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
//
// 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 of the results for students is equal
// to \sum\limits_{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 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 <= \frac{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} \in \{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 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
*/
//
public class C1622E {
  static final int MOD = (int)1e9+7;
  static final Random RAND = new Random();

  // https://codeforces.com/contest/1622/submission/140809534
  static int[] solve(int[] x, char[][] s) {
    int n = x.length;
    int m = s[0].length;
    int[] C = new int[m];
    int[] ans = new int[m];
    long maxsv = -1;

    // Consider all 2^n cases of set of students whose score is lower than expectation.
    // That is if (i & (1 << j)) == 0, then student j's score if lower then their expectation.
    for (int i = 0; i < (1 << n); i++) {
      long temp = 0;
      for (int j = 0; j < n; j++) {
        temp += (i & (1 << j)) == 0 ? x[j] : -x[j];
      }
      // Compute C[j] as count of up-votes for problem j (to maximize surprise value temp):
      //   * -1 from student with score lower than expectation and correct on j;
      //   *  0 from student with score lower than expectation and incorrect on j;
      //   *  1 from student with score higher than expectation and correct on j;
      //   * -1 from student with score higher than expectation and incorrect on j;
      Arrays.fill(C, 0);
      for (int k = 0; k < n; k++) {
        for (int j = 0; j < m; j++) {
          C[j] += (i & (1 << k)) == 0 ? '0' - s[k][j] : s[k][j] - '0';
        }
      }
      List<Integer> idxes = new ArrayList<>();
      for (int j = 0; j < m; j++) {
        idxes.add(j);
      }
      Collections.sort(idxes, (v, w) -> C[v] - C[w]);

      for (int j = 0; j < m; j++) {
        temp += (long)(j+1) * C[idxes.get(j)];
      }
      if (maxsv < temp) {
        maxsv = temp;
        for (int j = 0; j < m; j++) {
          ans[idxes.get(j)] = j + 1;
        }
      }
    }
    return ans;
  }

  static String trace(int[] a) {
    StringBuilder sb = new StringBuilder();
    for (int v : a) {
     if (sb.length() > 0) {
       sb.append(' ');
     }
      sb.append(v);
    }
    return sb.toString();
  }

  public static void main(String[] args) {
    Scanner in = getInputScanner();
    int T = in.nextInt();
    for (int t = 1; t <= T; t++) {
      int n = in.nextInt();
      int m = in.nextInt();
      int[] x = new int[n];
      for (int i = 0; i < n; i++) {
        x[i] = in.nextInt();
      }
      char[][] s = new char[n][m];
      for (int i = 0; i < n; i++) {
        String v = in.next();
        for (int j = 0; j < m; j++) {
          s[i][j] = v.charAt(j);
        }
      }
      int[] ans = solve(x, s);
      System.out.println(trace(ans));
    }
    in.close();
  }

  static Scanner getInputScanner() {
    try {
      final String USERDIR = System.getProperty("user.dir");
      final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
      final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
      return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
    } catch (Exception e) {
      return new Scanner(System.in);
    }
  }
}
