All submissions for this problem are available.

Bio-HRQ-Comparator

Bio-HRQ-Comparator is a fully automatic computer based neurological scanning

system that scans brains of three persons simultaneously and ranks them 1, 2, 3 with respect

to their HRQ (Human Resource Quotient) for a given activity. Bio-HRQ-Comparator has three

specially designed chairs each fitted with brain scanning devise. Exactly three persons are to

sit on the chairs and just think independently and simultaneously on the best possible solution

of a given problem related to an activity for which HRQ is tested. The thinking process

continues for a specified duration of time that is dependent on the complexity of the given

problem. Bio-HRQ-Comparator captures the thinking process and ranks them with respect to

their HRQ without any further scrutiny. Through rigorous testing and analysis, ranking by Bio-

HRQ-comparator has been found to be so precise that no two ranked persons are identified

to have different rank order or found to have the same HRQ.

The system has the potential to replace the traditional method of selection of

candidates through interview, where the basic problem is to arrive at total ordering and

ranking of a given set of n (assume n 20) candidates with respect to their HRQ for a specific

job. It is proposed to select arbitrarily k sets of three candidates each and rank candidates in

each set using Bio-HRQ-comparator hoping that total ordering and ranking of candidates can

be done successfully. However it is not always possible to arrive at total ordering and ranking

of all n candidates using arbitrarily selected k sets of candidates.

You are required to write a program that either ranks all n candidates, if possible,

using the k results obtained so far or determines the minimum number m of additional Bio-

HRQ-comparator testing required for determining the total ordering and ranking of all n

candidates. In case m additional testing are required, the program should identify m sets of

three candidates each, for additional Bio-HRQ-comparator testing. Assume for simplicity that

a candidate is not required to appear more than twice for additional testing.

Input

Input may contain multiple test cases. Each test case contains two lines.

The 1st line gives n and a string of n letters. Each letter in the string identifies a

candidate and letters appear in an arbitrary order.

The 2nd line gives k results of Bio-HRQ-comparator testing. The first field is the integer

k and it is followed by k strings of three letters each representing k results. The three letters in

a string appear in order of ranks 1, 2 and 3 of candidates represented by the letters.

Input terminates with a line that contains 0 (zero) as the first and the only character.

Output

For each test case, print output in one line.

The first field in the line gives the integer m. If m is equal to 0 then a string of n letters

follows it; the string represents the total rank order of all n candidates.

Otherwise m strings each of length three follow the integer m. Each string contains

either three letters or two letters followed by an asterisk (*). Each letter identifies a specified

candidate while an asterisk represents an option to have any candidate. Letters in a string

appear in alphabetic order and strings appear in lexicographic order.

Sample Input

5 axdpf

3 adf xdp axp

5 xapfd

3 afd xdp axf

7 adgbnem

4 aem egn dgm emb

0

Sample Output

1 fp*

0 axfdp

2 ade bmn