H :: Mastermind

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Mastermind is a code-breaking game for two players. One player is the code-maker, the other one is the code-breaker. The code-maker secretly chooses a code: an array of N integers C₁,C₂ ,..., C_n, each with a value in the range [1, k]  (Some numbers of [1, k] may not appear in the code, and some may appear more than once). N and k are set at the beginning of the game. The code-breaker tries to find the code through a number of guesses. Each guess itself is also similar to the code; an array of N integers g₁,g₂ ,..., g_nin the range[1, k] . After each guess, the code-maker provides the code-breaker with a hint showing the extent to which the guess matched the code. The hint consists of two numbers: the black points, and the white points. The black points is the number of correctly guessed slots, i.e. the number of indices i (1 ≤ i ≤ N) such that g_i = C_i. The white points shows the number of correctly guessed integers which appear in the code but not at the place they were in the guessed array. Each integer slot of the code (C_u) must be considered at most once during the calculation of the two hint points together, with a higher priority for the black points. For example if the code is “12234” and the guess is “22542”, then the black and white points will be 1 and 2 respectively.

You have just joined a friend of yours while she was playing Mastermind as the code-breaker. After a number of guesses and receiving the hints, she is asking if you could help her find all the possible solutions according to the current state of the game. You must write a program to find any possible code which is consistent with all the guesses and their respective hints.

Input

There are multiple test cases in the input. Each test case starts with a line containing three integers, N, k, and G - the number of guesses made up-to-now (1≤N≤20, 1≤k≤9, 0≤G≤100, and k^N≤10⁵). Then, G lines follow, showing the guesses and their respective hints. Each line starts with a string of N digits (in the range [1, k]) as the guess, followed by two space-separated integers as the black points and the white points for that guess. The input terminates with a line of the form “0 0 0” which should not be processed as a test case.

Output

For each test case, write all the possible solutions of the game in the lexicographic order. Each solution must be printed as a string of N digits (in the range [1, k]) in a single line. On the last line of output for each test case, write the total number of possible solutions in the format "Total: X".

 

Sample Input

4 4 1
1234 2 2
4 4 2
1234 2 2
4321 2 2
3 2 1
111 2 0
3 3 1
111 2 1
0 0 0

Sample Output

1243
1324
1432
2134
3214
4231
Total: 6
1324
4231
Total: 2
112
121
211
Total: 3
Total: 0

Submit

Source: 10th Iran Nationwide Internet Contest