Background

Special for algorithm lovers, ^_^

Description

对于一个长度为 $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$（可以为空），使得

   $$u_i = t_i \oplus \left(\bigoplus_{v \in T} v\right) $$

   其中 $\oplus$ 表示按位异或；

2. 在满足条件 1 的前提下，$u_i$ 的支撑序列字典序尽可能小。

对于两个序列 $A, B$，称 $A$ 的字典序小于 $B$ 当且仅当：

• $A$ 是 $B$ 的真前缀；
• 或存在第一个相异位置 $p$ 使得 $A_p < B_p$。

Format

Input

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

接下来 $n$ 行，每行一个长度为 $m$ 的 01 串 $s_i$。 接下来 $q$ 行，每行一个长度为 $m$ 的 01 串 $t_i$。

Output

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

Samples

1 3 2
110
010
101

100
101

解释：

• 第 1 组：可能的 $u_i$ 有 010 和 100，支撑序列分别为 $\[2]\$ 和$[1]$，字典序更小的是 $[1]$，对应 100。
• 第 2 组：可能的 $u_i$ 有 101 和 011，支撑序列分别为 $\[1,3]\$ 和$[2,3]$，字典序更小的是 $[1,3]$，对应 101。

2 4 4
1100
1010
1000
0001
0110
0011

1000
1101
0000
1111

解释：

1. 可能的结果：1000、0100、0010、1110，字典序最小支撑序列为 $[1]$ → 1000。
2. 可能的结果：0001、1101、1011、0111，最小支撑序列为 $[1,2,4]$ → 1101。
3. 可能的结果：0110、1010、1100、0000，最小支撑序列为空 → 0000。
4. 可能的结果：0011、1111、1001、0101，最小支撑序列为 $[1,2,3,4]$ → 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