장관들의 골칫거리
시간 제한2초메모리 제한1024 MB
각 장관이 최대 네 개의 법안에 던진 찬반 의견에서, 장관마다 자기 의견의 과반수가 만족되는 배정이 존재하는지 판정하고, 존재하면 모든 배정에서 값이 같은 법안을 가려낸다.
문제
외딴 나라 스타니스탄의 장관들은 의사 결정에 심각한 문제를 겪고 있다. 모든 것은 몇 주 전, 법안 통과 여부를 결정하는 새로운 절차가 도입되면서 시작되었다. 이 절차는 다음과 같이 진행된다. 각 표결 회의마다 여러 법안이 상정된다. 각 장관은 일부 법안에 대해 "찬성" 또는 "반대"로 의견을 표명한다. 실제 표결을 집계하는 기술적 해결책의 설계상 한계 때문에, 각 장관은 많아야 네 개의 서로 다른 법안에만 투표할 수 있다(대부분의 장관은 몇 가지 쟁점에만 관심이 있으므로 별문제는 되지 않는다). 그런 다음 이 표를 바탕으로, 각 장관이 자신의 의견 중 절반보다 많은 수가 반영되도록 통과할 법안을 선택한다.
예리한 독자라면 이미 알아차렸겠지만, 이 절차는 여러 문제를 일으킬 수 있다. 예를 들어 모든 장관을 만족시키는 선택이 여러 개라면 어떨까? 더 나쁘게는 모든 장관을 만족시키는 것이 불가능하다면? 그리고 장관들의 의견이 유일한 선택으로 이어진다 해도, 그 선택을 어떻게 찾을 것인가?
여러분의 임무는 이러한 문제를 해결하는 프로그램을 작성하는 것이다. 장관들의 표가 주어졌을 때, 모든 장관을 만족시킬 수 있는지 판별하고, 만족시킬 수 있다면 주어진 제약 아래에서 선택이 하나로 정해지는 법안에 대한 결정을 구해야 한다.
입력
입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 B(1 ≤ B ≤ 100)와 M(1 ≤ M ≤ 500)으로 시작한다. B는 표결할 서로 다른 법안의 수이고, M은 장관의 수이다. 다음 M개 줄은 장관들의 표를 나타낸다. 각 줄은 장관이 투표한 법안의 수를 나타내는 정수 1 ≤ k ≤ 4로 시작하고, 이어서 k개의 표가 주어진다. 각 표는 <bill> <vote> 형식이며, <bill>은 투표 대상 법안을 나타내는 1과 B 사이의 정수이고, <vote>는 장관의 의견이 "찬성"인지 "반대"인지를 나타내는 y 또는 n이다. 어떤 장관도 같은 법안에 두 번 투표하지 않는다. 마지막 테스트 케이스 다음에는 두 개의 0이 있는 줄이 온다.
출력
각 테스트 케이스마다 테스트 케이스 번호(1부터 시작)와 처리 결과를 출력한다. 모든 장관을 만족시킬 수 없다면 결과는 impossible이다. 그렇지 않다면 결과는 길이 B인 문자열이며, i번째 문자는 i번째 법안에 대한 결정이 "찬성"이어야 하면 y, "반대"여야 하면 n, 주어진 표만으로 결정이 정해지지 않으면 ?이다.