정답표 알아내기

얼마 전 한 학급이 시험을 봤다. 모든 문항이 참과 거짓 중 하나를 고르는 형식이었지만 난이도가 아주 높았다. 시험이 끝난 뒤 교재와 강의 노트를 뒤지고 서로 답을 맞춰 봐도 학생들은 정답이 무엇인지 확신하지 못했다. 교수에게 물어볼 수도 있지만, 무지를 드러내는 질문을 던질 만한 상대가 아니다. 그래도 자기가 어떻게 답했는지는 모두 정확히 기억한다.

교수가 답안지를 돌려줬는데 결과가 예상과 딴판이다. 어느 문항이 맞고 틀렸는지는 표시하지 않고, 맞힌 문항 수만 답안지 맨 위에 적어 놓았다. 그렇다면 교수가 생각한 정답표는 무엇일까. 점수가 예상과 워낙 동떨어져서 교수가 개수를 잘못 셌다고 의심하는 학생도 있다.

학생마다 적어 낸 답안과 맞힌 문항 수가 주어진다. 이 결과를 모두 설명하는 정답표를 구하라.

첫째 줄에 테스트 케이스의 개수가 주어진다. 이 값은 양수이고 100 이하이다. 각 테스트 케이스는 다음 형식이다.

• 첫째 줄에 학생 수 $n$과 문항 수 $m$이 공백으로 구분되어 주어진다 ($1 \le n \le 12$, $1 \le m \le 30$).
• 이어지는 $n$개 줄에 학생 한 명의 답안이 한 줄씩 주어진다. 각 줄은 0 또는 1로 이루어진 길이 $m$의 숫자열이고, 0은 거짓, 1은 참을 뜻한다. 그 뒤에 공백 하나를 두고 그 학생이 맞힌 문항 수 $c$가 주어진다 ($0 \le c \le m$).

테스트 케이스마다 한 줄씩 출력한다.

• 모든 결과를 설명하는 정답표가 정확히 하나면 0과 1로 이루어진 길이 $m$의 숫자열로 그 정답표를 출력한다.
• 그렇지 않으면 모든 결과를 설명하는 정답표의 개수를 출력하고, 공백 하나를 둔 뒤 solutions를 붙인다. 가능한 정답표가 하나도 없으면 0 solutions가 된다.