Hamming Distance

[littlehug]

Task Description

Write a program to correct communication errors. We are given N 8-bit valid codes stored in M 64-bit unsigned integers. These valid codes are used to communication, so we will receive P 8-bit text stored in unsigned characters. Unfortunately there could be errors during the transmission so some bits might be incorrect. After receiving these text, we want to know if the text is transmitted correctly. Even better, we want to recover their original contents by comparing them to the N valid codes. This is called error detection and correction.

We define the hamming distance between two binary integers as the number of different bits in corresponding positions. For example, the hamming distance of 1001 and 1110 is 3, since they differ in 3 positions.

Now it is simple to understand that if every pair of valid codes has a hamming distance of 3 or larger, then we can correct one bit error. The idea is that if we receive a text, there will not exist a pair of valid codes that both have hamming distance 1 from the text. If we guarantee that there will be no more than 1 bit of error, we can uniquely identify the original valid code of this text.

Assume that we can only fix one bit error, we will do the following when given a text t.

• If there t is a valid code, i.e., the hamming distance between them is zero, then the text is correct and we print the text.
• If there exists a valid code C with hamming distance 1 from the text, it means the text has 1-bit error, therefore the original valid code is C, and we print C. It is guaranteed that C is unique.
• In all other cases the text cannot be fixed. We ignore it without print anything.

Note that the store of valid codes in the 64-bit unsigned integer starts from MSB (the most significant bit).

Let us illustrate the task with an examples. We are given eight valid codes stored in a 64-bit unsigned integer (3689656785894203750) and three texts (85, 83, 211).

valid codes	text
0011001100110100010010110100110001010010010101010110000101100110	010101010101001111010011

The first text 01010101 is correct and we print 01010101. The second text 01010011 has 1-bit error, and we fix it to the valid code 01010010. The third text 11010011 is incorrect and cannot be fixed so we do not print anything.

Subtask

• 10 points: The number of valid codes N is a multiple of 8, and every text is correct.
• 40 points: The number of valid codes N is a multiple of 8, and all texts are possible.
• 50 points: The number of valid codes N may not be a multiples of 8, and all texts are possible.

Notes

The format specifier of unsigned character:

unsigned char uc;
scanf("%hhu", &uc);
printf("%hhu", uc);

Input format

The input contains only one test case. The first line contains three integers N, M and P, where N is the number of valid code, M is the number of 64-bit unsigned integer which store the valid codes, and P is the number of text. The following M lines are 64-bit unsigned integers, and the next P lines are 8-bit unsigned characters.

Output format

Print the correct codes on separate lines.

Sample Input 1

8 1 6
148385984830076570
91
2
118
68
44
154

Sample Output 1

91
2
118
68
44
154

Sample Input 2

8 1 3
3689656785894203750
85
83
211

Sample Output 2

85
82

Sample Input 3

10 2 6
145556837624335960
7451487058461196288
85
104
172
44
79
106

Sample Output 3

105
44
44
78