#8966. 「洛谷 P12060」[THUPC 2025 决赛] Now or Never 暂未评定

对于一个长度为 的 01 串 ，定义其支撑序列 为 的一个子序列，其中 当且仅当 。例如，。特别地，全零串的支撑序列为空序列 。

给定一个 01 串集合 ，其中包含 个长度为 的 01 串 。再给定 组询问，第 组询问给出一个长度为 的 01 串 。你需要输出一个长度为 的 01 串 满足以下条件：

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

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

输入的第一行三个正整数 ，分别表示集合 的大小、01 串的长度以及询问组数。

接下来 行，第 行一个长度为 的 01 串 。

最后 行，第 行一个长度为 的 01 串 描述一组询问。

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

样例输入 1

复制1 3 2
110
010
101

样例输出 1

复制100
101

样例输入 2

复制2 4 4
1100
1010
1000
0001
0110
0011

样例输出 2

复制1000
1101
0000
1111

样例输入 3

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

样例输出 3

复制111101101
110110001
110111001
111100010
111111010
111110111
111111011

样例输入 4

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

样例输出 4

复制111111111100001001010011
111111101111001101010101
111111101100001011000101
111111101101110101111011
111111111111000010111011
111111111111110101011010
111111101110101001001101
111111101101111110011010
111111111110100001000000

样例 #1 解释

对于第一组测试数据，满足第一个条件的串有 010 和 100。二者支撑序列分别为 ，，其中字典序更小的是 。

对于第二组测试数据，满足第一个条件的串有 101 和 011。二者支撑序列分别为 ，，其中字典序更小的是 。

样例 #2 解释

对于第一组测试数据，满足第一个条件的串有 1000、0100、0010 和 1110，其中字典序最小的支撑序列是 。

对于第二组测试数据，满足第一个条件的串有 0001、1101、1011 和 0111，其中字典序最小的支撑序列是 。

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

对于第四组测试数据，满足第一个条件的串有0011、1111、1001 和 0101，其中字典序最小的支撑序列是 。

提示

题目名称是什么意思？

来源与致谢

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

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