给定一个包含 $n$ 个位串的序列 $b_1, b_2, \dots, b_n$，每个位串的长度均为 $k \times 4$ 位。 同时给定另一个包含 $m$ 个位串的序列 $a_1, a_2, \dots, a_m$，每个位串的长度也均为 $k \times 4$ 位。

令 $f(x)$ 表示满足以下条件的最小索引 $i$：存在 $b_1, b_2, \dots, b_i$ 的一个非空子集，其异或和等于 $x$。如果不存在这样的索引，则 $f(x) = -1$。

请输出 $f(a_1), f(a_2), \dots, f(a_m)$ 的值。

输入格式

输入的第一行包含三个整数 $n$ ($1 \le n \le 1,000$)，$m$ ($1 \le m \le 1,000$) 和 $k$ ($1 \le k \le 40$)，其中 $n$ 是序列 $b$ 的长度，$m$ 是序列 $a$ 的长度，两个序列中的元素均为长度为 $k \times 4$ 位的位串。

接下来的 $n$ 行，每行包含一个长度为 $k$ 的十六进制字符串，表示 $b_i$。这些字符串仅由十六进制数字（'0'–'9' 和 'a'–'f'）组成。

随后接下来的 $m$ 行，每行包含一个与上述格式相同的十六进制字符串，表示 $a_i$。

输出格式

输出 $m$ 行，每行一个整数，其中第 $i$ 行的整数为 $f(a_i)$。

样例

输入 1

3 5 2
02
e1
fa
02
e3
1b
e1
ff

输出 1

1
2
3
2
-1

输入 2

5 6 2
01
02
04
08
10
01
02
03
04
05
64

输出 2

1
2
2
3
3
-1