← 返回题目列表

Codeforces · 1622/E

E. 数学测试

中文机器翻译题面 查看原题

Petya 是一名数学老师。他的 $$$n$$$ 学生编写了包含 $$$m$$$ 问题的测试。对于每个学生来说,都知道他回答正确了哪些问题,没有回答了哪些问题。

如果学生正确回答第 $$$j$$$ 题,他将获得 $$$p_j$$$ 分(否则,他将获得 $$$0$$$ 分)。此外,问题的分数以这样的方式分布:数组 $$$p$$$ 是从 $$$1$$$ 到 $$$m$$$ 的数字排列。

对于第 $$$i$$$ 个学生,Petya 知道他期望在测试中获得 $$$x_i$$$ 分。佩蒂亚想知道结果会有多么出乎意料。 Petya 认为,学生成绩的惊喜值等于 $$$\sum\limits_{i=1}^{n} |x_i - r_i|$$$,其中 $$$r_i$$$ 是第 $$$i$$$ 个学生在测试中获得的分数。

你的任务是帮助 Petya 找到这样一个排列 $$$p$$$,其中结果的惊喜值最大。如果有多个答案,请打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10$$$; $$$1 \le m \le 10^4$$$) - 分别是学生人数和问题数量。

第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i \le \frac{m(m+1)}{2}$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 个学生期望获得的分数。

接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含字符串 $$$s_i$$$ ($$$|s_i| = m; s_{i, j} \in \{0, 1\}$$$),其中 $$$s_{i, j}$$$ 是 $$$1$$$,如果第 $$$i$$$ 学生有正确回答第 $$$j$$$ 问题,否则回答 $$$0$$$。

所有测试用例的 $$$m$$$ 总和不超过 $$$10^4$$$。

输出

对于每个测试用例,打印 $$$m$$$ 整数 - 一个排列 $$$p$$$,其中结果的意外值是最大可能的。如果有多个答案,请打印其中任何一个。

示例

输入 #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