Mastermind: The Best Next Guess

Mastermind is a two-player game. The first player, the codemaker, secretly chooses a code of $l$ characters, where each character is one of $c$ colors written as the uppercase letters A, B, C, ... (the first $c$ letters of the alphabet). The second player, the codebreaker, tries to discover the code by making guesses; each guess is itself a string of $l$ such letters.

After each guess the codemaker reports two numbers using black and white pegs. The number of black pegs is the count of positions that have the correct color in the correct place. The number of white pegs is the count of the remaining correct colors that appear in the code but in a different position. For example, if the secret code is ABCC and the guess is ACCD, the response is 2 black and 1 white; if the guess is CCAA, the response is 3 white. The codebreaker keeps guessing until the response is $l$ black pegs, which means the code has been found.

Suppose $n$ guesses have already been made and answered. A code is still possible if it is consistent with every one of those $n$ responses. For a candidate next guess — which may be any length-$l$ code over the $c$ colors, not only a still-possible one — consider every response it could produce. For each such response, count how many still-possible codes would give that response; if the response is $l$ black pegs the code is fully determined, so that response leaves 0 codes. The largest of these counts, taken over all responses, is the uncertainty of the candidate guess. The best next guess is the one with the smallest uncertainty.

For example, suppose only three codes are still possible: ABBB, ABBC, and ABCB. Guessing ABBB gives two responses: 4 black (the code is found, 0 left) or 3 black (which leaves 2 codes, ABBC and ABCB), so its uncertainty is 2. Guessing ABBC instead gives three responses: 4 black (0 left), 3 black (1 left, ABBB), and 2 black 2 white (1 left, ABCB), so its uncertainty is 1. Thus ABBC is the better guess here.

Given the guesses and responses so far, write a program that reports the best next guess.

The first line contains a single integer $T$, the number of test cases. Each test case consists of several lines. The first line holds three integers $l$, $c$, and $n$: the length of the code, the number of colors, and the number of guesses already made, with $1 \le l \le 15$, $1 \le c \le 20$, and $0 \le n \le 10$. The values of $l$ and $c$ are always such that the total number of possible codes, $c^l$, is at most $32768$. Each of the next $n$ lines has the form

guess b w

where $guess$ is a length-$l$ string, and $b$ and $w$ are the numbers of black and white pegs in its response. Every color is an uppercase letter taken from the first $c$ letters of the alphabet. For each test case, the given guesses leave at most $1500$ codes still possible.

For each test case, output one line containing the best next guess and its uncertainty, separated by a single space. If several guesses share the smallest uncertainty, output the one that comes first in alphabetical (lexicographic) order.