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 
#include <iostream>
#include <cstdio>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iterator>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define x0 abc
#define y0 ABC
#define x1 abcd
#define y1 ABCD
#define xn abcde
#define yn ABCDE

#define lb lower_bound
#define ub upper_bound

#define in insert
#define er erase

#define fi first
#define se second
#define mp make_pair

#define pb push_back
#define pob pop_back

#define uns unsigned

#define ld long double
#define ll long long

#define cont continue
#define re return

#define MAXLL 9000000000000000000LL
#define MAXINT 2000000000

#define MINLL -9000000000000000000LL
#define MININT -2000000000

#define pi acos(-1.)

#define endl '\n'

#define OUT cout << "-------" << endl;

using namespace std;

using namespace __gnu_pbds;

typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

pair <ll, ll> d[12001];

char c[111][12001];

ll a[12001], b[12001], ans[12001], n, m, i, j, z, t, sum, mx;

    void solve()
    {
        cin >> n >> m;

        for (i = 1; i <= n; i++) cin >> a[i];

        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++) cin >> c[i][j];

        mx = -1;

        for (z = 0; z < (1LL < n); z++) {
            for (i = 0; i < n; i++)
                if ((z >> i) % 2 == 1) b[i + 1] = 1;
                else b[i + 1] = -1;

            for (j = 1; j <= m; j++) {
                sum = 0;

                for (i = 1; i <= n; i++)
                    if (c[i][j] == '1') sum += b[i];

                d[j] = mp(sum, j);
            }

            sort(d + 1, d + m + 1);

            sum = 0;

            for (i = 1; i <= n; i++) sum += a[i] * b[i] * -1;

            for (i = 1; i <= m; i++) sum += d[i].fi * i;

            if (sum > mx) {
                mx = sum;

                for (i = 1; i <= m; i++) ans[i] = d[i].se;
            }
        }

        for (i = 1; i <= m; i++) cout << ans[i] << " ";

        cout << endl;
    }

int main()
{
    //freopen("maxxor.in", "r", stdin);
    //freopen("maxxor.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;

    while (t--) solve();

    re 0;
}
