P12060 [THUPC 2025 决赛] Now or Never

对于一个长度为 $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 解释 对于第一组测试数据，满足第一个条件的串有 `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 官方仓库 。