Math Test
Contest: Educational Codeforces Round 120 (Rated for Div. 2)
Difficulty rating: 2200
Tags: bitmasks, brute force, greedy

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 $$$\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 surprise value of the results is maximum possible. If there are multiple answers, print any of them.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10$$$; $$$1 \le m \le 10^4$$$) — the number of students and the number of questions, respectively.

The second line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le \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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example output:
3 1 2 
2 3 4 1 
3 1 4 5 2 6

Editorial:
Note that there are only two ways to fix the result of the operation of taking an absolute value in the expression $$$|x_i - r_i|$$$: $$$x_i - r_i$$$ or $$$r_i - x_i$$$. Since the value of $$$n$$$ is small enough that we can iterate over all $$$2^n$$$ options, and choose the one for which the sum is maximum.
For each student, let's fix with which sign their total points will contribute to the answer, then $$$x_i$$$ will contribute with the opposite sign. Now, for the question $$$j$$$ we can calculate $$$val_j$$$ — the coefficient with which $$$p_j$$$ will contribute to the answer. It remains to choose such a permutation $$$p$$$ that the sum $$$\sum\limits_{j=1}^m p_j val_j$$$ is the maximum possible. From here we can see that if $$$val_j < val_i$$$ (for some $$$i$$$ and $$$j$$$), then $$$p_j < p_i$$$ must holds, otherwise we can swap $$$p_j$$$ and $$$p_i$$$, and the answer will increase. This means that we can sort all questions in ascending order by the value in the $$$val$$$ array, and assign the value $$$x$$$ in the array $$$p$$$ to the $$$x$$$-th question in ascending order.
For some of $$$2^n$$$ options, the permutations we found may be illegal because it can happen that we consider the case that some $$$|x_i - r_i|$$$ evaluates as $$$(x_i - r_i)$$$, but in the best permutation we found for that option, it evaluates as $$$(r_i - x_i)$$$. We can just ignore it because this will never be the case with the option giving the highest possible surprise value — if this thing happened for some option to choose the signs of $$$r_i$$$, then, if we flip the signs for the students such that the conditions on them are not met in the optimal permutation, we'll get a combination of signs that yields a higher surprise value.