{"problem":{"name":"紫丁香","description":{"content":"对于一个字符串 $A$，记 $A_i$ 表示它的第 $i$ 个字符。 设 $S$ 是任意长度为 $m$ 的 $01$ 串。我们有 $n$ 个操作，第 $i$ 个操作可以表示成一个定义域和值域都是长度为 $m$ 的 $01$ 串集合的函数 $f_i$，表示经过这次操作后 $S$ 会变成 $f_i(S)$。而函数 $f_i$ 可以由一个长度为 $m$ 的串 $T_i$ 表示，$T_i$ 由 $\\te","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9393"},"statements":[{"statement_type":"Markdown","content":"对于一个字符串 $A$，记 $A_i$ 表示它的第 $i$ 个字符。\n\n设 $S$ 是任意长度为 $m$ 的 $01$ 串。我们有 $n$ 个操作，第 $i$ 个操作可以表示成一个定义域和值域都是长度为 $m$ 的 $01$ 串集合的函数 $f_i$，表示经过这次操作后 $S$ 会变成 $f_i(S)$。而函数 $f_i$ 可以由一个长度为 $m$ 的串 $T_i$ 表示，$T_i$ 由 $\\texttt{0,1,-}$ 三种字符组成，其中：\n\n- $T_{i,j}=\\texttt{0}$ 表示 $[f_i(S)]_j=\\texttt{0}$。\n\n- $T_{i,j}=\\texttt{1}$ 表示 $[f_i(S)]_j=\\texttt{1}$。\n\n- $T_{i,j}=\\texttt{-}$ 表示 $[f_i(S)]_j=S_j$。\n\n也就是说，每个操作会将 $S$ 的一些位赋值为 $0$，一些位赋值为 $1$，还有一些位不变。\n\n现在有 $q$ 次操作，每次操作给定一个长度为 $m$ 的 $01$ 串 $S$，你可以对它做任意多次操作，操作的顺序任意，一个操作可以做多次。得到的串 $S'$ 可以被看做一个二进制数，求对应二进制数最大的 $S'$。\n\n## Input\n\n第一行：三个整数 $m,n,q$。\n\n接下来 $n$ 行：每行一个长度为 $m$ 的串 $T$，表示一种操作。\n\n接下来 $q$ 行：每行一个长度为 $m$ 的串 $S$，表示一个询问。\n\n## Output\n\n输出 $q$ 行：每行一个长度为 $m$ 的串，依次表示每个询问的答案。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n对于第一个询问串 $\\texttt{00000}$，可以依次进行操作 $3,2$，得到最优的 $S'$：\n\n$$\\texttt{00000}\\to \\texttt{00010}\\to \\texttt{01110}$$\n\n对于第二个询问串 $\\texttt{10010}$，可以依次进行操作 $1,3$，得到最优的 $S'$：\n\n$$\\texttt{10010}\\to \\texttt{11001}\\to \\texttt{11010}$$\n\n对于第三个询问串 $\\texttt{00101}$，可以依次进行操作 $3,2$，得到最优的 $S'$：\n\n$$\\texttt{00101}\\to \\texttt{00010}\\to \\texttt{01110}$$\n\n---\n\n**【数据范围】**\n\n对于全部数据：$1\\leq m\\leq 22$，$1\\leq n,q\\leq 10^5$，$T$ 仅包含 $\\texttt{0,1,-}$ 三种字符，$S$ 仅包含 $\\texttt{0,1}$ 两种字符。\n\n|     子任务编号     | $m\\leq$ | $n\\leq$ | $q\\leq$ |         特殊性质          | 分值 |\n| :----------------: | :-----: | :-----: | :-----: | :-----------------------: | :--: |\n| $\\text{Subtask 1}$ |  $10$   | $1000$  |   $1$   |            无             | $10$ |\n| $\\text{Subtask 2}$ |  $10$   | $1000$  | $1000$  |            无             | $20$ |\n| $\\text{Subtask 3}$ |  $20$   | $10^5$  | $10^5$  | $T$ 中没有 $\\texttt{-}$ | $10$ |\n| $\\text{Subtask 4}$ |  $18$   | $10000$ |   $10$   |            无             | $18$ |\n| $\\text{Subtask 5}$ |  $20$   | $10^5$  |   $10$   |            无             | $18$ |\n| $\\text{Subtask 6}$ |  $22$   | $10^5$  | $10^5$  |            无             | $24$ |\n\n---\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/793whkzq.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9393","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["5 3 3\n-1-01\n011-0\n--010\n00000\n10010\n00101\n","01110\n11010\n01110\n"]],"created_at":"2026-03-03 11:09:25"}}