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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class E {

  /**
   * Template @author William Fiset, william.alexandre.fiset@gmail.com
   */
  static InputReader in = new InputReader(System.in);
  private static StringBuilder sb;

  static class InputReader {

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static final InputStream DEFAULT_STREAM = System.in;
    private static final int MAX_DECIMAL_PRECISION = 21;
    private int c;
    private byte[] buf;
    private int bufferSize, bufIndex, numBytesRead;

    private InputStream stream;

    private static final byte EOF = -1;
    private static final byte NEW_LINE = 10;
    private static final byte SPACE = 32;
    private static final byte DASH = 45;
    private static final byte DOT = 46;

    private char[] charBuffer;

    private static byte[] bytes = new byte[58];
    private static int[] ints = new int[58];
    private static char[] chars = new char[128];

    static {
      char ch = ' ';
      int value = 0;
      byte _byte = 0;
      for (int i = 48; i < 58; i++) {
        bytes[i] = _byte++;
      }
      for (int i = 48; i < 58; i++) {
        ints[i] = value++;
      }
      for (int i = 32; i < 128; i++) {
        chars[i] = ch++;
      }
    }

    private static final double[][] doubles = {
      {0.0d, 0.00d, 0.000d, 0.0000d, 0.00000d, 0.000000d, 0.0000000d, 0.00000000d, 0.000000000d,
        0.0000000000d, 0.00000000000d, 0.000000000000d,
        0.0000000000000d, 0.00000000000000d, 0.000000000000000d, 0.0000000000000000d,
        0.00000000000000000d, 0.000000000000000000d,
        0.0000000000000000000d, 0.00000000000000000000d, 0.000000000000000000000d},
      {0.1d, 0.01d, 0.001d, 0.0001d, 0.00001d, 0.000001d, 0.0000001d, 0.00000001d, 0.000000001d,
        0.0000000001d, 0.00000000001d, 0.000000000001d,
        0.0000000000001d, 0.00000000000001d, 0.000000000000001d, 0.0000000000000001d,
        0.00000000000000001d, 0.000000000000000001d,
        0.0000000000000000001d, 0.00000000000000000001d, 0.000000000000000000001d},
      {0.2d, 0.02d, 0.002d, 0.0002d, 0.00002d, 0.000002d, 0.0000002d, 0.00000002d, 0.000000002d,
        0.0000000002d, 0.00000000002d, 0.000000000002d,
        0.0000000000002d, 0.00000000000002d, 0.000000000000002d, 0.0000000000000002d,
        0.00000000000000002d, 0.000000000000000002d,
        0.0000000000000000002d, 0.00000000000000000002d, 0.000000000000000000002d},
      {0.3d, 0.03d, 0.003d, 0.0003d, 0.00003d, 0.000003d, 0.0000003d, 0.00000003d, 0.000000003d,
        0.0000000003d, 0.00000000003d, 0.000000000003d,
        0.0000000000003d, 0.00000000000003d, 0.000000000000003d, 0.0000000000000003d,
        0.00000000000000003d, 0.000000000000000003d,
        0.0000000000000000003d, 0.00000000000000000003d, 0.000000000000000000003d},
      {0.4d, 0.04d, 0.004d, 0.0004d, 0.00004d, 0.000004d, 0.0000004d, 0.00000004d, 0.000000004d,
        0.0000000004d, 0.00000000004d, 0.000000000004d,
        0.0000000000004d, 0.00000000000004d, 0.000000000000004d, 0.0000000000000004d,
        0.00000000000000004d, 0.000000000000000004d,
        0.0000000000000000004d, 0.00000000000000000004d, 0.000000000000000000004d},
      {0.5d, 0.05d, 0.005d, 0.0005d, 0.00005d, 0.000005d, 0.0000005d, 0.00000005d, 0.000000005d,
        0.0000000005d, 0.00000000005d, 0.000000000005d,
        0.0000000000005d, 0.00000000000005d, 0.000000000000005d, 0.0000000000000005d,
        0.00000000000000005d, 0.000000000000000005d,
        0.0000000000000000005d, 0.00000000000000000005d, 0.000000000000000000005d},
      {0.6d, 0.06d, 0.006d, 0.0006d, 0.00006d, 0.000006d, 0.0000006d, 0.00000006d, 0.000000006d,
        0.0000000006d, 0.00000000006d, 0.000000000006d,
        0.0000000000006d, 0.00000000000006d, 0.000000000000006d, 0.0000000000000006d,
        0.00000000000000006d, 0.000000000000000006d,
        0.0000000000000000006d, 0.00000000000000000006d, 0.000000000000000000006d},
      {0.7d, 0.07d, 0.007d, 0.0007d, 0.00007d, 0.000007d, 0.0000007d, 0.00000007d, 0.000000007d,
        0.0000000007d, 0.00000000007d, 0.000000000007d,
        0.0000000000007d, 0.00000000000007d, 0.000000000000007d, 0.0000000000000007d,
        0.00000000000000007d, 0.000000000000000007d,
        0.0000000000000000007d, 0.00000000000000000007d, 0.000000000000000000007d},
      {0.8d, 0.08d, 0.008d, 0.0008d, 0.00008d, 0.000008d, 0.0000008d, 0.00000008d, 0.000000008d,
        0.0000000008d, 0.00000000008d, 0.000000000008d,
        0.0000000000008d, 0.00000000000008d, 0.000000000000008d, 0.0000000000000008d,
        0.00000000000000008d, 0.000000000000000008d,
        0.0000000000000000008d, 0.00000000000000000008d, 0.000000000000000000008d},
      {0.9d, 0.09d, 0.009d, 0.0009d, 0.00009d, 0.000009d, 0.0000009d, 0.00000009d, 0.000000009d,
        0.0000000009d, 0.00000000009d, 0.000000000009d,
        0.0000000000009d, 0.00000000000009d, 0.000000000000009d, 0.0000000000000009d,
        0.00000000000000009d, 0.000000000000000009d,
        0.0000000000000000009d, 0.00000000000000000009d, 0.000000000000000000009d}
    };

    public InputReader() {
      this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE);
    }

    public InputReader(int bufferSize) {
      this(DEFAULT_STREAM, bufferSize);
    }

    public InputReader(InputStream stream) {
      this(stream, DEFAULT_BUFFER_SIZE);
    }

    public InputReader(InputStream stream, int bufferSize) {
      if (stream == null || bufferSize <= 0) {
        throw new IllegalArgumentException();
      }
      buf = new byte[bufferSize];
      charBuffer = new char[128];
      this.bufferSize = bufferSize;
      this.stream = stream;
    }

    private byte read() throws IOException {

      if (numBytesRead == EOF) {
        throw new IOException();
      }

      if (bufIndex >= numBytesRead) {
        bufIndex = 0;
        numBytesRead = stream.read(buf);
        if (numBytesRead == EOF) {
          return EOF;
        }
      }

      return buf[bufIndex++];
    }

    private void doubleCharBufferSize() {
      char[] newBuffer = new char[charBuffer.length << 1];
      for (int i = 0; i < charBuffer.length; i++) {
        newBuffer[i] = charBuffer[i];
      }
      charBuffer = newBuffer;
    }

    private int readJunk(int token) throws IOException {

      if (numBytesRead == EOF) {
        return EOF;
      }

      do {

        while (bufIndex < numBytesRead) {
          if (buf[bufIndex] > token) {
            return 0;
          }
          bufIndex++;
        }

        numBytesRead = stream.read(buf);
        if (numBytesRead == EOF) {
          return EOF;
        }
        bufIndex = 0;

      } while (true);

    }

    public byte nextByte() throws IOException {
      return (byte) nextInt();
    }

    public int nextInt() throws IOException {

      if (readJunk(DASH - 1) == EOF) {
        throw new IOException();
      }
      int sgn = 1, res = 0;

      c = buf[bufIndex];
      if (c == DASH) {
        sgn = -1;
        bufIndex++;
      }

      do {

        while (bufIndex < numBytesRead) {
          if (buf[bufIndex] > SPACE) {
            res = (res << 3) + (res << 1);
            res += ints[buf[bufIndex++]];
          } else {
            bufIndex++;
            return res * sgn;
          }
        }

        numBytesRead = stream.read(buf);
        if (numBytesRead == EOF) {
          return res * sgn;
        }
        bufIndex = 0;

      } while (true);

    }

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

    public void close() throws IOException {
      stream.close();
    }

    public long nextLong() throws IOException {
      if (readJunk(DASH - 1) == EOF) {
        throw new IOException();
      }
      int sgn = 1;
      long res = 0L;
      c = buf[bufIndex];
      if (c == DASH) {
        sgn = -1;
        bufIndex++;
      }
      do {
        while (bufIndex < numBytesRead) {
          if (buf[bufIndex] > SPACE) {
            res = (res << 3) + (res << 1);
            res += ints[buf[bufIndex++]];
          } else {
            bufIndex++;
            return res * sgn;
          }
        }
        numBytesRead = stream.read(buf);
        if (numBytesRead == EOF) {
          return res * sgn;
        }
        bufIndex = 0;
      } while (true);
    }

    public String nextString() throws IOException {
      if (numBytesRead == EOF) {
        return null;
      }
      if (readJunk(SPACE) == EOF) {
        return null;
      }

      for (int i = 0;;) {
        while (bufIndex < numBytesRead) {
          if (buf[bufIndex] > SPACE) {
            if (i == charBuffer.length) {
              doubleCharBufferSize();
            }
            charBuffer[i++] = (char) buf[bufIndex++];
          } else {
            bufIndex++;
            return new String(charBuffer, 0, i);
          }
        }

        // Reload buffer
        numBytesRead = stream.read(buf);
        if (numBytesRead == EOF) {
          return new String(charBuffer, 0, i);
        }
        bufIndex = 0;
      }
    }
  }

  static boolean[][] personGotQuestion;

  public static void main(String[] args) throws IOException {
    PrintWriter out = new PrintWriter(System.out);
    int T = in.nextInt();
    for (int tt = 0; tt < T; tt++) {
      int nPeople = in.nextInt();
      int nQuestions = in.nextInt();
      int[] expectedScores = in.nextIntArray(nPeople);
      personGotQuestion = new boolean[nPeople][nQuestions];
      for (int person = 0; person < nPeople; person++) {
        char[] line = in.nextString().toCharArray();
        for (int q = 0; q < nQuestions; q++) {
          personGotQuestion[person][q] = line[q] == '1';
        }
      }

      ArrayList<Integer>[] count = new ArrayList[1 << nPeople];
      for (int q = 0; q < nQuestions; q++) {
        int mask = 0;
        for (int p = 0; p < nPeople; p++) {
          mask += (1 << p) * (personGotQuestion[p][q] ? 1 : 0);
        }
        if (count[mask] == null) {
          count[mask] = new ArrayList<>();
        }
        count[mask].add(q);
      }
      int nNonzero = 0;
      for (ArrayList<Integer> l : count) {
        if (l != null) {
          nNonzero++;
        }
      }
      Question[] questions = new Question[nNonzero];
      nNonzero = 0;
      for (int mask = 0; mask < 1 << nPeople; mask++) {
        if (count[mask] == null) {
          continue;
        }
        questions[nNonzero++] = new Question(mask, count[mask]);
      }
      long best = 0;
      int bestMask = 0;
      for (int mask = 0; mask < 1 << nPeople; mask++) {
        //if this is a 1 bit, expected is positive
        long constantToAdd = 0;
        for (int i = 0; i < nPeople; i++) {
          if ((mask & (1 << i)) != 0) {
            constantToAdd += expectedScores[i];
          } else {
            constantToAdd -= expectedScores[i];
          }
        }

        long bestOtherDist = bestOtherDist(mask, nQuestions, nPeople, questions, false);
        if (bestOtherDist + constantToAdd > best) {
          best = bestOtherDist + constantToAdd;
          bestMask = mask;
        }

//				System.out.println("For mask "+mask+" "+constantToAdd+" "+bestOtherDist);
      }
//			out.println(best+" "+bestMask);
      finalAns = new int[nQuestions];
      bestOtherDist(bestMask, nQuestions, nPeople, questions, true);
      for (int i = 0; i < nQuestions; i++) {
        out.print(finalAns[i] + " ");
      }
      out.println();
    }
    out.close();
  }

  static int[] finalAns;

  static long bestOtherDist(int mask, int nQuestions, int nPeople,
  Question[] questions, boolean markAns) {
    for (Question q : questions) {
      q.netValue = 0;
      for (int i = 0; i < nPeople; i++) {
        if ((q.mask & (1 << i)) != 0) {
          if ((mask & (1 << i)) != 0) {
            q.netValue--;
          } else {
            q.netValue++;
          }
        }
      }
    }
    Arrays.sort(questions);
    long ans = 0;
    int next = 1;
    for (Question qq : questions) {
//			for (int i=0; i<qq.count; i++) {
//				ans+=next*qq.netValue;
//				next++;
//			}
      for (int i : qq.originalPositions) {
        ans += next * qq.netValue;
        if (markAns) {
          finalAns[i] = next;
        }
        next++;
      }
    }
    return ans;
  }

  static class Question implements Comparable<Question> {

    int mask;
    int netValue;
    int count;
    ArrayList<Integer> originalPositions;

    public Question(int mask, ArrayList<Integer> originalPositions) {
      this.mask = mask;
      this.count = originalPositions.size();
      this.originalPositions = originalPositions;
    }

    public int compareTo(Question o) {
      return Integer.compare(netValue, o.netValue);
    }
  }

  static final Random random = new Random();
  static final int mod = 1_000_000_007;

  static void ruffleSort(int[] a) {
    int n = a.length;//shuffle, then sort 
    for (int i = 0; i < n; i++) {
      int oi = random.nextInt(n), temp = a[oi];
      a[oi] = a[i];
      a[i] = temp;
    }
    Arrays.sort(a);
  }

  static long add(long a, long b) {
    return (a + b) % mod;
  }

  static long sub(long a, long b) {
    return ((a - b) % mod + mod) % mod;
  }

  static long mul(long a, long b) {
    return (a * b) % mod;
  }

  static void sort(int[] a) {
    ArrayList<Integer> l = new ArrayList<>();
    for (int i : a) {
      l.add(i);
    }
    Collections.sort(l);
    for (int i = 0; i < a.length; i++) {
      a[i] = l.get(i);
    }
  }
}
