题目描述

对于一个字符串 $A$，记 $A_i$ 表示它的第 $i$ 个字符。

设 $S$ 是任意长度为 $m$ 的 $01$ 串。我们有 $n$ 个操作，第 $i$ 个操作可以表示成一个定义域和值域都是长度为 $m$ 的 $01$ 串集合的函数 $f_i$，表示经过这次操作后 $S$ 会变成 $f_i(S)$。而函数 $f_i$ 可以由一个长度为 $m$ 的串 $T_i$ 表示，$T_i$ 由 $\texttt{0,1,-}$ 三种字符组成，其中：

• $T_{i,j}=\texttt{0}$ 表示 $[f_i(S)]_j=\texttt{0}$。

• $T_{i,j}=\texttt{1}$ 表示 $[f_i(S)]_j=\texttt{1}$。

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

也就是说，每个操作会将 $S$ 的一些位赋值为 $0$，一些位赋值为 $1$，还有一些位不变。

现在有 $q$ 次操作，每次操作给定一个长度为 $m$ 的 $01$ 串 $S$，你可以对它做任意多次操作，操作的顺序任意，一个操作可以做多次。得到的串 $S'$ 可以被看做一个二进制数，求对应二进制数最大的 $S'$。

输入格式

第一行：三个整数 $m,n,q$。

接下来 $n$ 行：每行一个长度为 $m$ 的串 $T$，表示一种操作。

接下来 $q$ 行：每行一个长度为 $m$ 的串 $S$，表示一个询问。

输出格式

输出 $q$ 行：每行一个长度为 $m$ 的串，依次表示每个询问的答案。

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

01110
11010
01110

提示

【样例解释】

对于第一个询问串 $\texttt{00000}$，可以依次进行操作 $3,2$，得到最优的 $S'$：

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

对于第二个询问串 $\texttt{10010}$，可以依次进行操作 $1,3$，得到最优的 $S'$：

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

对于第三个询问串 $\texttt{00101}$，可以依次进行操作 $3,2$，得到最优的 $S'$：

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

---

【数据范围】

对于全部数据：$1\leq m\leq 22$，$1\leq n,q\leq 10^5$，$T$ 仅包含 $\texttt{0,1,-}$ 三种字符，$S$ 仅包含 $\texttt{0,1}$ 两种字符。

子任务编号	$m\leq$	$n\leq$	$q\leq$	特殊性质	分值
$\text{Subtask 1}$	$10$	$1000$	$1$	无	$10$
$\text{Subtask 2}$			$1000$		$20$
$\text{Subtask 3}$	$20$	$10^5$		$T$ 中没有 $\texttt{-}$	$10$
$\text{Subtask 4}$	$18$	$10000$	$10$	无	$18$
$\text{Subtask 5}$	$20$	$10^5$
$\text{Subtask 6}$	$22$		$10^5$		$24$

---