Bài kiểm tra Toán

Có $n$ học sinh làm một bài kiểm tra gồm $m$ câu hỏi. Với mỗi học sinh, ta biết câu nào em làm đúng và câu nào em làm sai.

Nếu một học sinh trả lời đúng câu thứ $j$, em được $p_j$ điểm; nếu sai, em được $0$ điểm. Mảng điểm $p$ phải là một hoán vị của $1,2,\dots ,m$ (tức là mỗi giá trị từ $1$ đến $m$ xuất hiện đúng một lần).

Với học sinh thứ $i$, em kỳ vọng đạt được $x_i$ điểm. Gọi $r_i$ là số điểm thực tế học sinh thứ $i$ đạt được sau khi chấm theo hoán vị $p$. Đặt giá trị bất ngờ của kết quả là:

$$\sum _{i=1}^n|x_i-r_i|.$$

Hãy tìm hoán vị $p$ sao cho giá trị bất ngờ là lớn nhất có thể. Nếu có nhiều hoán vị thỏa mãn, in ra một hoán vị bất kỳ.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ($1\le t\le {10}^4$) — số test.

Mỗi test có cấu trúc:

• Dòng 1: hai số nguyên $n$ và $m$ ($1\le n\le 10$; $1\le m\le {10}^4$).
• Dòng 2: $n$ số nguyên $x_1,x_2,\dots ,x_n$ ($0\le x_i\le \frac{m(m+1)}{2}$).
• Tiếp theo là $n$ dòng, mỗi dòng là một xâu $s_i$ độ dài $m$ gồm các ký tự $0$ và $1$. Ký tự $s_{i,j}$ bằng $1$ nếu học sinh $i$ trả lời đúng câu $j$.

Tổng $m$ trên tất cả các test không vượt quá ${10}^4$.

Dữ liệu ra

Với mỗi test, in ra $m$ số nguyên là một hoán vị $p$ làm cho giá trị bất ngờ lớn nhất. Nếu có nhiều đáp án, in một hoán vị bất kỳ.

Ví dụ