Make a Guess

MasterMind is a logic game created in 1971 by Mordechai Meirovitz, a telecommunications engineer from Romania. It won the prestigious "Game of the Year" award in 1974 and was a major commercial success, sold in more than 40 countries.

In MasterMind, your goal as a player is to discover a secret password chosen by your opponent. The password is a sequence of characters drawn from a given alphabet. To find it, you submit guesses. A guess is a candidate password: a string with the same length as the password, using characters from the same alphabet.

After each guess you receive an answer made of two integers $(E, G)$ describing how good the guess was.

• If a character of the guess appears in the password at the same position, it counts as "excellent" and is added to $E$.
• Otherwise, if a character appears in both the guess and the password but at a different position, it counts as "good" and is added to $G$.
• A single character of the guess is never counted twice (if it is counted as excellent, it is not also counted as good).

The table below shows some examples.

By combining several guesses and their answers, a player can eventually deduce the password. Given a set of guesses and their answers, determine everything that can be established about the password: print the character at every position that is uniquely determined, and print '?' at every position that cannot be determined.

The input contains several test cases. The first line of each test case has three integers $N$, $L$, and $K$, where $N$ is the number of guesses ($0 \le N \le 1000$), $L$ is the length of the password ($1 \le L \le 4$), and $K$ is the size of the alphabet ($1 \le K \le 18$). The next line contains the $K$ characters of the alphabet, with no separators; each is a digit ('0'–'9') or an uppercase letter ('A'–'Z'). Each of the following $N$ lines contains one guess (a string of $L$ characters from the alphabet) followed by its answer, the two integers $E$ and $G$.

The end of the input is marked by a line with $N = L = K = 0$, which must not be processed.

The input must be read from standard input.

For each test case, print one line with everything that can be established from the guesses and answers. Among all passwords consistent with every guess and answer, if the character at some position is always the same, print that character; otherwise print '?' at that position. In particular, if the guesses and answers are contradictory so that no password is consistent with them, print '?' at every position.

The output must be written to standard output.