Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 1754
Who Wants to Have the Fastest Fingers?

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A television game show host begins each new game by selecting a player, as follows. The host asks candidate players to order four items. The first candidate to order the items correctly wins. If there is a tie for the fastest time, or if no one correctly answers, the host poses a new question. The producers air only questions that select a player. They are unhappy with their current player selection software and are seeking a replacement.

The candidates have at most 30 seconds to answer the question. During this time, they press buttons A, B, C, or D, indicating how to order the items. Pressing a special rub out button marked X erases the last selection (this has no effect if there are no characters to rub out). For example, after pressing BXXACXDXBDC, the candidate has selected the answer ABDC. Each candidate's selection is sent to the software along with a timestamp (from 0 to 300, in tenths of a second) and a number identifying the candidate. A candidate cannot make simultaneous selections (i.e., with the same timestamp), but two different candidates might make selections at the same time. Although the software receives the messages in time sequence for a particular candidate, messages from two different candidates may arrive out of time sequence. For example, the software might receive the following sequence:

 Candidate Timestamp Selection Interpretation 1 20 B Candidate 1 selected B at time 20 (answer: B) 2 10 B Candidate 2 selected B at time 10 (answer: B) 1 50 C Candidate 1 selected C at time 50 (answer: BC) 2 40 D Candidate 2 selected D at time 40 (answer: BD) 1 70 X Candidate 1 erased C at time 70 (answer: B) 1 110 D Candidate 1 selected D at time 110 (answer: BD) 1 120 A Candidate 1 selected A at time 120 (answer: BDA) 2 100 A Candidate 2 selected A at time 100 (answer: BDA) 2 150 C Candidate 2 selected C at time 150 (answer: BDAC) 1 170 C Candidate 1 selected C at time 170 (answer: BDAC)

Suppose that the correct item order is BDAC. To be considered correct, a candidate's final answer must exactly match the correct item order. In this example, both candidates have the correct answer, but Candidate 2 has the faster time (15.0 seconds), and is the player for the next round.

Input

The input contains several player selection rounds. Each round begins with a line containing two integers m and n separated by whitespace, where 2 <= m <= 10 is the number of candidates and n is the number of messages. The next line contains only the letters A, B, C, and D, in the correct order for that round; each letter appears exactly once and in upper case. The next n lines contain the messages in the following format:

candidate timestamp selection

where candidate is an integer between 1 and m inclusive that identifies the candidate sending the message, timestamp is an integer between 0 and 300 inclusive representing the time in tenths of a second, and selection is either A, B, C, D, or X (in upper case) as explained above. Your program must stop processing input when it encounters a data set in which n is 0.

Output

Begin the output of each player selection round by summarizing the results. List the candidates in order of candidate number and state whether the candidate was correct or incorrect. If the candidate was correct, indicate the time at which the candidate completed data entry. If a player is selected, indicate which player. If no player is selected, indicate that this question should not be aired and a new question is needed. Leave a blank line between the output for different player selection rounds. Follow the format shown in the Sample Output.

Sample Input

2 10
BDAC
1 20 B
2 10 B
1 50 C
2 40 D
1 70 X
1 110 D
1 120 A
2 100 A
2 150 C
1 170 C
2 8
ABCD
1 20 A
1 25 B
1 78 D
2 15 C
2 59 D
2 105 A
2 189 B
1 187 C
2 0

Sample Output

Round #1:  2 candidates
Candidate 1:  Correct in 17.0 seconds
Candidate 2:  Correct in 15.0 seconds
Candidate 2 is selected as the player for this round.

Round #2:  2 candidates
Candidate 1:  Incorrect
Candidate 2:  Incorrect
Don't air this one...we need a new question.

Source: Southeast USA 2000
Submit    Status