Books

The Noname State University (NSU) is preparing for a new type of programming contest. Each university in this contest can be represented only by a single team of two students. There is also the official list of $N$ books which the contestants must read to perform successfully. There is little time left before the contest, and not every student is able to read all books in time.

Every student knows for each set of books whether she can read it in time. There are $M$ students willing to participate in the contest in the NSU. The coach prepared a list of $K$ candidate teams. To choose a single team for the contest, she wants to know each team's reading capability.

A team has read a book if at least one member of the team has read it. Your task is to find, for each candidate team and for each set of books, whether the team members can plan their training so that the team will have read all the books of this set in time.

The first line of the input contains three integers: $N$ (number of books), $M$ (number of students), and $K$ (number of candidate teams). The constraints are $1 \le N \le 21$, $2 \le M \le 6$, and $1 \le K \le 6$. Zero-based numbering is used everywhere in this problem.

The $i$-th of the next $M$ lines defines the capabilities of the $i$-th student. The capabilities are a string $S_i$ of length $2^N$ containing 0's and 1's. The $k$-th character of the string is 1 if and only if the student can read the set of books with bitmask $k$ in time. The bitmask is defined as follows.

Number the books from 0 to $N-1$. Let $X$ be a set of books, and let $a_j = 1$ if book $j$ belongs to $X$, and $a_j = 0$ otherwise. The bitmask of $X$ is $k = \sum_{j=0}^{N-1} a_j 2^j.$ The $i$-th student can read $X$ in time if and only if the $k$-th character of $S_i$ is 1.

The $t$-th of the next $K$ lines describes the $t$-th candidate team. It contains two integers $a_t$ and $b_t$, the numbers of the two students in the team ($0 \le a_t, b_t < M$, $a_t \neq b_t$).

The capabilities satisfy two guarantees. First, if a student can read a set of books, she can read every subset of it. Second, a student can always read the empty set, so the first character of her string is always 1.

Print $K$ lines, each containing $2^N$ characters 0 or 1. The $t$-th line gives the capabilities of the $t$-th team in the same format as the students' strings in the input. The $k$-th character of the $t$-th line is 1 if and only if the team can read the set $X$ of books with bitmask $k$ in time.

The 0-th student can read one of the following sets: $\emptyset$, $\{0\}$, $\{1\}$, $\{2\}$, $\{0, 1\}$, $\{1, 2\}$. The first student can only read book 0 (or nothing). The second student can read either book 0 or book 2 (or nothing). The third and fourth students can read any single book (or nothing).

The 0-th team is able to read all the books if student 0 reads books $\{1, 2\}$ and student 1 reads book 0. It is easy to check that the team can also read any other set of books.

The 1st team can read books 0 and 2 if its members read different books. The team can also read any subset of $\{0, 2\}$.

In the 2nd team, each member can read at most one book. Hence, the team together can read any set of two or fewer books.