P9393 Lilac

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.

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 $q$ lines: each line contains a length-$m$ string, giving the answer to each query in order.

**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}$ | $10$ | $1000$ | $1000$ | None | $20$ | | $\text{Subtask 3}$ | $20$ | $10^5$ | $10^5$ | No $\texttt{-}$ in $T$ | $10$ | | $\text{Subtask 4}$ | $18$ | $10000$ | $10$ | None | $18$ | | $\text{Subtask 5}$ | $20$ | $10^5$ | $10$ | None | $18$ | | $\text{Subtask 6}$ | $22$ | $10^5$ | $10^5$ | None | $24$ | ---  Translated by ChatGPT 5