ZOJ Problem Set - 3636
Every day, there are countless data be transmitted in the fiber, optic cable or in the air. The form of the data is 0 or 1, and when the receiver gets the data, it has to use some method to decode them before process them.
To simplify this problem, we assume each of the data is a 0-1 vector of length N. For example, 00001111 is a vector of length 8. We call the vector a code.
To express a variety of data, we need some different codes, and we will use the combination of them. The combination of code v1 and code v2 is a new code v3, which has the same length with v1 and v2, and the ith bit of v3 is the sum of the ith bit of v1 and v2 module 2. For example, the combination of 00001111 and 00001010 is 00000101. Notice that if combine a code with itself, you'll get a code which all bits are 0. By this, the sender can send a code in the given code set or the combination of two or more codes in that set.
But there is an annoying problem that, after the transmission in the media, it maybe cause some errors in the code, and it will drive the receiver mad because it does not know which is the original code it should be.
An error makes a bit in the vector reverse, at that bit, 0 turns to 1 or 1 turns to 0. Fortunately, the probability of errors occur is low. In this problem, the number of errors in each code is less than 3, that means in one code there are at most 3 bits is reversed than the original code.
Your task is to help the receiver decode such codes. With each received code, you need to find the original code with the least errors, or point out that it can not be decoded with errors less than 3.
There are multiple test cases. For each test case:
The first line contains three integers N(1≤N≤30), K(1≤K≤20000), M(1≤M≤1000). N is the length of every codes, K is the number of elements in the given code set, M is the number of codes received.
Next K lines, each line contains a 0-1 string of length N, represents a code in the given set.
Next M lines, each line contains a 0-1 string of length N, represents a code received.
There is a blank line between every two cases.
Process to the end of input.
M lines each case, if the code received can be decode, show the original code which with the least errors in the corresponding line, else show "NA". If there are more than one legal answers, show the minimum by lexicographic order.
4 3 3 0011 1100 1010 1111 1010 1000 5 1 2 00001 00000 11111
1111 1010 0000 00000 NA
Author: LI, Huang
Contest: ZOJ Monthly, August 2012