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