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).
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.
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.
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.
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).
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
Notes
The format specifier of unsigned character:
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
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3