E. Тест по математике
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Петя — учитель по математике. $$$n$$$ его студентов написали тест, состоящий из $$$m$$$ вопросов. Для каждого студента известно на какие вопросы он ответил верно, а на какие нет.

Если студент правильно ответил на $$$j$$$-й вопрос, он получает $$$p_j$$$ баллов (иначе он получает $$$0$$$ баллов). Причем баллы за вопросы распределены так, что массив $$$p$$$ является перестановкой чисел от $$$1$$$ до $$$m$$$.

Для $$$i$$$-го студента Петя знает, что он ожидает получить $$$x_i$$$ баллов за тест. Пете стало интересно, насколько неожиданными могут быть результаты. Петя считает, что неожиданность результатов для студентов равна $$$\sum\limits_{i=1}^{n} |x_i - r_i|$$$, где $$$r_i$$$ — количество баллов, которое $$$i$$$-й студент получил за тест.

Ваша задача — помочь Пете, найти такую перестановку $$$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$$$, для которой неожиданность результатов максимальна. Если оптимальных ответов несколько, выведите любой из них.

Пример
Входные данные
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
Выходные данные
3 1 2 
2 3 4 1 
3 1 4 5 2 6