책 읽기

노네임 주립대학교(NSU)는 새로운 형식의 프로그래밍 대회를 준비하고 있다. 이 대회에서 각 대학은 두 명의 학생으로 이루어진 팀 하나로만 대표될 수 있다. 대회에서 좋은 성적을 내려면 참가자가 읽어야 하는 공식 도서 목록에 $N$권의 책이 있다. 대회까지 남은 시간이 얼마 없고, 모든 학생이 제시간에 모든 책을 읽을 수 있는 것은 아니다.

각 학생은 책의 부분집합마다 제시간에 읽을 수 있는지 알고 있다. NSU에서 이 대회에 참가하려는 학생은 $M$명이다. 코치는 후보 팀 $K$개의 목록을 준비했다. 코치는 대회에 나갈 팀을 고르기 위해 각 팀의 독서 능력을 알고 싶어 한다.

팀 구성원 가운데 한 명이라도 어떤 책을 읽었다면, 팀도 그 책을 읽은 것으로 본다. 여러분의 과제는 각 후보 팀과 책의 부분집합마다, 팀원들이 훈련 계획을 세워 그 부분집합의 책을 모두 제시간에 읽을 수 있는지 판단하는 것이다.

입력의 첫 줄에는 세 정수 $N$(책의 수), $M$(학생 수), $K$(후보 팀 수)가 주어진다. 범위는 $1 \le N \le 21$, $2 \le M \le 6$, $1 \le K \le 6$이다. 이 문제의 모든 번호는 0부터 시작한다.

다음 $M$개의 줄 중 $i$번째 줄은 $i$번째 학생의 능력을 나타낸다. 능력은 길이가 $2^N$이고 0과 1로 이루어진 문자열 $S_i$로 주어진다. 문자열의 $k$번째 문자가 1이면 그 학생은 비트마스크가 $k$인 책의 집합을 제시간에 읽을 수 있고, 0이면 읽을 수 없다. 비트마스크는 다음과 같이 정한다.

책에 0부터 $N-1$까지 번호를 붙인다. 책의 집합 $X$에 대해, 책 $j$가 $X$에 속하면 $a_j = 1$, 아니면 $a_j = 0$으로 둔다. $X$의 비트마스크는 $k = \sum_{j=0}^{N-1} a_j 2^j$이다. $i$번째 학생이 $X$를 제시간에 읽을 수 있는 것은 $S_i$의 $k$번째 문자가 1일 때뿐이다.

다음 $K$개의 줄은 후보 팀을 설명한다. $t$번째 줄에는 $t$번째 팀을 이루는 두 학생의 번호 $a_t$, $b_t$가 주어진다($0 \le a_t, b_t < M$, $a_t \neq b_t$).

각 학생의 능력에는 두 가지 조건이 보장된다. 첫째, 학생이 어떤 책의 집합을 읽을 수 있으면 그 부분집합도 모두 읽을 수 있다. 둘째, 학생은 항상 공집합을 읽을 수 있으므로 문자열의 첫 문자는 항상 1이다.

$K$개의 줄을 출력한다. 각 줄은 0과 1로 이루어진 $2^N$개의 문자이다. $t$번째 줄은 $t$번째 팀의 능력을 입력에 주어진 학생의 문자열과 같은 형식으로 나타낸다. 즉, $t$번째 줄의 $k$번째 문자는 $t$번째 팀이 비트마스크가 $k$인 책의 집합 $X$를 제시간에 읽을 수 있을 때에만 1이다.

0번 학생은 $\emptyset$, $\{0\}$, $\{1\}$, $\{2\}$, $\{0, 1\}$, $\{1, 2\}$ 중 하나의 집합을 읽을 수 있다. 1번 학생은 0번 책만 읽을 수 있다(또는 아무것도 읽지 못한다). 2번 학생은 0번 책이나 2번 책 중 하나를 읽을 수 있다(또는 아무것도 읽지 못한다). 3번과 4번 학생은 책 한 권이면 어느 것이든 읽을 수 있다(또는 아무것도 읽지 못한다).

0번 팀은 0번 학생이 $\{1, 2\}$를 읽고 1번 학생이 0번 책을 읽으면 모든 책을 읽을 수 있다. 이 팀이 다른 어떤 책의 집합도 읽을 수 있다는 것은 쉽게 확인할 수 있다.

1번 팀은 두 구성원이 서로 다른 책을 읽으면 0번 책과 2번 책을 읽을 수 있다. 이 팀은 $\{0, 2\}$의 임의의 부분집합도 읽을 수 있다.

2번 팀의 구성원은 누구도 책을 한 권보다 많이 읽을 수 없다. 따라서 팀 전체로는 두 권 이하의 책으로 이루어진 어떤 집합이든 읽을 수 있다.