题目描述

对于一个长度为 $l$ 的 01 串 $w=w_1w_2\dots w_l$，定义其支撑序列 $\mathrm{supp}(w)$ 为 $[1, 2, \dots, l]$ 的一个子序列，其中 $i\in \mathrm{supp}(w)$ 当且仅当 $w_i = 1$。例如，$\mathrm{supp}(001100110) = [3, 4, 7, 8]$。特别地，全零串的支撑序列为空序列 $\varepsilon$。

给定一个 01 串集合 $S$，其中包含 $n$ 个长度为 $m$ 的 01 串 $s_1, s_2, \dots, s_n$。再给定 $q$ 组询问，第 $i$ 组询问给出一个长度为 $m$ 的 01 串 $t_i$。你需要输出一个长度为 $m$ 的 01 串 $u_i$ 满足以下条件：

1. 存在一个 $S$ 的子集 $T$，其中 $T$ 可以为空也可以为 $S$ 本身，满足 $u_i = t_i \oplus \bigoplus_{v \in T} v$，其中 $\oplus$ 表示按位异或操作，即 $u_i$ 为 $t_i$ 与 $T$ 中所有 01 串的异或和；
2. 在以上条件的基础之上，$u_i$ 的支撑序列的字典序尽可能小。

对于两个序列 $A, B$，称 $A$ 的字典序小于 $B$，当且仅当 $A$ 是 $B$ 的一个真前缀，或者 $A$ 和 $B$ 在第一个相异的位置 $p$ 上满足 $A_p < B_p$。

输入格式

输入的第一行三个正整数 $n, m, q\ (1\le n, m, q\le 2000)$，分别表示集合 $S$ 的大小、01 串的长度以及询问组数。

接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的 01 串 $s_i$。

最后 $q$ 行，第 $i$ 行一个长度为 $m$ 的 01 串 $t_i$ 描述一组询问。

输出格式

对于第 $i$ 组询问输出一行表示满足题设条件的长度为 $m$ 的 01 串 $u_i$。

1 3 2
110
010
101

100
101

2 4 4
1100
1010
1000
0001
0110
0011

1000
1101
0000
1111

3 9 7
011001111
101110001
110010100
010110110
101010100
000101101
001011100
100011111
100111000
001000101

111101101
110110001
110111001
111100010
111111010
111110111
111111011

9 24 9
100001011101000000000000
100011001100100001000000
010101000010100111110100
101110000010101110110010
100110110010011100000000
111111000010100101111011
000010110001001011010101
010101100111000010100111
111001111111000000000000
111000110110110000000000
011100101000100001000000
101001101000111011001100
100011100011110001000000
100001001011000000000000
101110110001111100000000
100011100101100010110000
101001001100101011000000
100101100110100111000000

111111111100001001010011
111111101111001101010101
111111101100001011000101
111111101101110101111011
111111111111000010111011
111111111111110101011010
111111101110101001001101
111111101101111110011010
111111111110100001000000

提示

样例 #1 解释

对于第一组测试数据，满足第一个条件的串有 010 和 100。二者支撑序列分别为 $\mathrm{supp}(010) = [2]$，$\mathrm{supp}(100) = [1]$，其中字典序更小的是 $[1]$。

对于第二组测试数据，满足第一个条件的串有 101 和 011。二者支撑序列分别为 $\mathrm{supp}(101) = [1, 3]$，$\mathrm{supp}(011) = [2, 3]$，其中字典序更小的是 $[1, 3]$。

样例 #2 解释

对于第一组测试数据，满足第一个条件的串有 1000、0100、0010 和 1110，其中字典序最小的支撑序列是 $\mathrm{supp}(1000) = [1]$。

对于第二组测试数据，满足第一个条件的串有 0001、1101、1011 和 0111，其中字典序最小的支撑序列是 $\mathrm{supp}(1101) = [1, 2, 4]$。

对于第三组测试数据，满足第一个条件的串有 0110、1010、1100 和 0000，其中字典序最小的支撑序列是 $\mathrm{supp}(0000) = \varepsilon$，也即空序列。

对于第四组测试数据，满足第一个条件的串有0011、1111、1001 和 0101，其中字典序最小的支撑序列是 $\mathrm{supp}(1111) = [1, 2, 3, 4]$。

提示

题目名称是什么意思？

来源与致谢

来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。