Ranklist Reconstruction

The developers of ProgCont are working on a new version of the system. The software is still in an initial phase; therefore, it provides very short answers after evaluations: it informs the contestants only whether their solution has been accepted or not. Unfortunately, during its first deployment, an unexplainable error occurred: the ranklist crashed. Help the organizers reconstruct the flow of the contest by executing some queries based on submission data.

Input Specification

The first line of the input contains two integers: the number of submissions S and the number of queries Q (1 ≤ S ≤ 5 000, 1 ≤ Q ≤ 10 000). This is followed by S lines, each containing the data of a submission. These lines are at most 50 characters long and contain the following space-separated values:

• the name of the submitting team (string without spaces),
• the identifier of a problem (string without spaces),
• the number of minutes passed since the start of the contest (nonnegative integer less than 300),
• the result of the evaluation (“true” or “false” depending on whether the solution has been accepted or not).

The last Q lines of the input each contains the parameters of a query in the form time team, where time is the time of the query expressed as the number of minutes passed since the start of the contest, and team is the identifier of a team.

Output Specification

The program should determine for each query all the data that appeared in the ranklist regarding the given team at the given time of the contest. These lines should contain the following values in the format of the sample output:

• the identifier of the team in the query,
• the number of minutes passed since the start of the contest,
• the number of problems solved by the team until the time of the query,
• penalty time calculated based on the submission times and the number of failed attempts at the time of the query,
• and the rank of the team at the time of the query.

Clarifications

• Ranking of the teams and the calculation of penalty times is based on a simplified rule. A team with more correct solutions is ranked higher. If two teams have the same number of correct solutions, then the one with less penalty time is ranked higher. If the penalty times are also the same, then the team submitting its first accepted solution sooner is ranked higher.
• Penatly time is given to a team regarding a given problem if the team has solved that problem. In this case, penalty time is the number of minutes passed since the start of the contest till the submission of the correct solution, plus 20 minutes as many times as the number of incorrect solutions submitted by the team for the given problem before the submission of the correct solution. The total penalty time of a team is the sum of penalty times for each problem.
• There will be no ties. The queries will contain only teams having at least one submission. Teams with no accepted solutions appear in the ranklist without a rank (see the sample output).
• The times of queries specify closed time intervals, i.e., a query in minute T should consider the solutions submitted in minute T. All times in this problem come from the range [0, 299]. A team may submit more than one solution at the same time, and no teams will work on a problem after a solution has been accepted for it.

Sample Input

1. 7 9
2. TeamC D 40 true
3. TeamA A 10 false
4. TeamB B 40 false
5. TeamA A 15 false
6. TeamA A 17 true
7. TeamD A 20 false
8. TeamE A 13 false
9. 0 TeamA
10. 10 TeamA
11. 15 TeamA
12. 17 TeamA
13. 299 TeamA
14. 299 TeamB
15. 299 TeamC
16. 299 TeamD
17. 299 TeamE

download as text file

Output for Sample Input

1. TeamA (0): 0 0 -
2. TeamA (10): 0 0 -
3. TeamA (15): 0 0 -
4. TeamA (17): 1 57 #1
5. TeamA (299): 1 57 #2
6. TeamB (299): 0 0 -
7. TeamC (299): 1 40 #1
8. TeamD (299): 0 0 -
9. TeamE (299): 0 0 -

download as text file