For a binary string $w = w_1w_2 \dots w_l$ of length $l$, we define its support sequence $\text{supp}(w)$ as the subsequence of $[1, 2, \dots, l]$ such that $i \in \text{supp}(w)$ if and only if $w_i = 1$. For example, $\text{supp}(001100110) = [3, 4, 7, 8]$. Specifically, the support sequence of the all-zero string is the empty sequence $\varepsilon$.

Given a set $S$ of $n$ binary strings $s_1, s_2, \dots, s_n$, each of length $m$. Given $q$ queries, where the $i$-th query provides a binary string $t_i$ of length $m$. You need to output a binary string $u_i$ of length $m$ that satisfies the following conditions:

1. There exists a subset $T$ of $S$ (where $T$ can be empty or $S$ itself) such that $u_i = t_i \oplus (\bigoplus_{v \in T} v)$, where $\oplus$ denotes the bitwise XOR operation, meaning $u_i$ is the XOR sum of $t_i$ and all strings in $T$.
2. Subject to the above condition, the support sequence of $u_i$ is lexicographically as small as possible.

For two sequences $A$ and $B$, $A$ is lexicographically smaller than $B$ if and only if $A$ is a proper prefix of $B$, or at the first position $p$ where $A$ and $B$ differ, $A_p < B_p$.

Input

The first line contains three positive integers $n, m, q$ ($1 \le n, m, q \le 2000$), representing the size of the set $S$, the length of the binary strings, and the number of queries, respectively.

The next $n$ lines each contain a binary string $s_i$ of length $m$.

The last $q$ lines each contain a binary string $t_i$ of length $m$, describing a query.

Output

For each query $i$, output a single line containing the binary string $u_i$ of length $m$ that satisfies the conditions.

Examples

Input 1

1 1 3 2
2 110
3 010
4 101

Output 1

100
101

Note

For the first test case, the strings satisfying the first condition are $010$ and $100$. Their support sequences are $\text{supp}(010) = [2]$ and $\text{supp}(100) = [1]$, respectively. The lexicographically smaller one is $[1]$.

For the second test case, the strings satisfying the first condition are $101$ and $011$. Their support sequences are $\text{supp}(101) = [1, 3]$ and $\text{supp}(011) = [2, 3]$, respectively. The lexicographically smaller one is $[1, 3]$.

Input 2

2 4 4
1100
1010
1000
0001
0110
0011

Output 2

1000
1101
0000
1111

Note

For the first test case, the strings satisfying the first condition are $1000, 0100, 0010$, and $1110$, among which the lexicographically smallest support sequence is $\text{supp}(1000) = [1]$.

For the second test case, the strings satisfying the first condition are $0001, 1101, 1011$, and $0111$, among which the lexicographically smallest support sequence is $\text{supp}(1101) = [1, 2, 4]$.

For the third test case, the strings satisfying the first condition are $0110, 1010, 1100$, and $0000$, among which the lexicographically smallest support sequence is $\text{supp}(0000) = \varepsilon$, the empty sequence.

For the fourth test case, the strings satisfying the first condition are $0011, 1111, 1001$, and $0101$, among which the lexicographically smallest support sequence is $\text{supp}(1111) = [1, 2, 3, 4]$.

Input 3

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

Output 3

111101101
110110001
110111001
111100010
111111010
111110111
111111011

Input 4

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

Output 4

111111111100001001010011
111111101111001101010101
111111101100001011000101
111111101101110101111011
111111111111000010111011
111111111111110101011010
111111101110101001001101
111111101101111110011010
111111111110100001000000

Hint

What does the problem name mean?