Math Test

题意翻译

有$n$个学生参加考试，考试有$m$道题，已知每个学生做对了哪些题，$p_{i,j}=1$表示学生$i$做对了第$j$题得到此题的分数，为0则没有得分，每个学生有一个预期得分$r_i$，老师的惊喜值$suprise=\sum_{i=1}^n \left| r_i-s_i\right|$，$s_i$为每个学生的实际得分，请给每道题安排一个分数，使得这些题的分数是一个$1\dots n$的排列，且老师的惊喜值最大，输出每道题的分数。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

3 1 2 
2 3 4 1 
3 1 4 5 2 6