题目描述

对于一个长度为 $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 \left(\bigoplus_{v \in T} v\right)$，其中 $\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

对于第一组测试数据，满足第一个条件的串有 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 4 4
1100
1010
1000
0001
0110
0011

1000
1101
0000
1111

对于第一组测试数据，满足第一个条件的串有 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]$。

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

提示

题目名称是什么意思？

题目使用协议

来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2025 官方仓库（https://gitlink.org.cn/thusaa/thupc2025final）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。