10329번 - Key to Knowledge 다국어

A while ago a class of students took an exam. It consisted of true-or-false questions only, but the questions were really tough! Even afterward, with the help of the book, lecture notes and each other, the students are not sure what all the correct answers were. They could ask the professor of course, but he is not the kind of guy you would dare to disturb with questions that betray your ignorance. Anyway, the students at least have an idea of how they performed.

The professor has just returned the exams, but the results are not quite as expected. Unfortunately, he did not indicate on their exams which answers were right or wrong, he has simply put the number of correct answers at the top. So what were the correct answers according to the professor then? Given how far off some of the grades are from expected, there is a suspicion among some of the students that the professor did not count the correct answers properly.

Given, for each student, the answers he/she gave and the number of correct answers, can you work out what set of correct answers matches the results?

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with two space-separated integers n and m (1 ≤ n ≤ 12 and 1 ≤ m ≤ 30): the number of students and the number of questions in the exam, respectively.
• n lines, each with m digits, each digit either 0 or 1: the answers given by each student, with 0 representing “false” and 1 representing “true”. This is followed by a space and a single integer c (0 ≤ c ≤ m): the number of correct answers for that student.

Per test case:

• one line with m digits, each one either 0 or 1: the unique set of correct answers that could account for all the results. If there is not exactly one such set, the line should read “# solutions” instead, with the number of solutions in place of ‘#’.