Problem Description

For a string $A$, let $A_i$ denote its $i$-th character.

Let $S$ be a $01$ string of length $m$. We have $n$ operations. The $i$-th operation can be represented as a function $f_i$ whose domain and codomain are both the set of length-$m$ $01$ strings, meaning that after this operation, $S$ becomes $f_i(S)$. The function $f_i$ can be described by a length-$m$ string $T_i$, where $T_i$ consists of the three characters $\texttt{0,1,-}$, and:

• $T_{i,j}=\texttt{0}$ means $[f_i(S)]_j=\texttt{0}$.

• $T_{i,j}=\texttt{1}$ means $[f_i(S)]_j=\texttt{1}$.

• $T_{i,j}=\texttt{-}$ means $[f_i(S)]_j=S_j$.

That is, each operation sets some bits of $S$ to $0$, some bits to $1$, and leaves the remaining bits unchanged.

Now there are $q$ queries. In each query, you are given a length-$m$ $01$ string $S$. You may apply the operations any number of times, in any order, and an operation may be used multiple times. The resulting string $S'$ can be viewed as a binary number. Find the $S'$ that corresponds to the maximum possible binary number.

Input Format

The first line contains three integers $m,n,q$.

The next $n$ lines: each line contains a length-$m$ string $T$, describing an operation.

The next $q$ lines: each line contains a length-$m$ string $S$, describing a query.

Output Format

Output $q$ lines: each line contains a length-$m$ string, giving the answer to each query in order.

5 3 3
-1-01
011-0
--010
00000
10010
00101

01110
11010
01110

Hint

Sample Explanation

For the first query string $\texttt{00000}$, you can apply operations $3,2$ in order to obtain the optimal $S'$:

$$\texttt{00000}\to \texttt{00010}\to \texttt{01110}$$

For the second query string $\texttt{10010}$, you can apply operations $1,3$ in order to obtain the optimal $S'$:

$$\texttt{10010}\to \texttt{11001}\to \texttt{11010}$$

For the third query string $\texttt{00101}$, you can apply operations $3,2$ in order to obtain the optimal $S'$:

$$\texttt{00101}\to \texttt{00010}\to \texttt{01110}$$

---

Constraints

For all testdata: $1\leq m\leq 22$, $1\leq n,q\leq 10^5$. $T$ contains only $\texttt{0,1,-}$, and $S$ contains only $\texttt{0,1}$.

Subtask ID	$m\leq$	$n\leq$	$q\leq$	Special Property	Score
$\text{Subtask 1}$	$10$	$1000$	$1$	None	$10$
$\text{Subtask 2}$			$1000$		$20$
$\text{Subtask 3}$	$20$	$10^5$		No $\texttt{-}$ in $T$	$10$
$\text{Subtask 4}$	$18$	$10000$	$10$	None	$18$
$\text{Subtask 5}$	$20$	$10^5$
$\text{Subtask 6}$	$22$		$10^5$		$24$

---

Translated by ChatGPT 5