Zeyu is making his first ever Sadness Contest! His contest consists of problems (numbered from to ) with contestants participating (numbered from to ).
The rules of his contests are as follows:
- The contest lasts for minutes.
- Each contestant may submit at most times to each problem.
- Contestants are ordered by the number of problems solved. The more problems they solved, the better their rank.
- If there is a tie in the number of problems solved, then contestants are ordered by the sum of the times used to solve the problems (in minutes) starting from the beginning of the contest, plus minutes for each incorrect submission to a problem they solved. Note that there is no penalty for incorrect submissions to problem that they did not solve. The smaller their sum of times plus penalty, the better their rank.
- If there is also a tie in the sum of times plus penalty, then the contestants are ordered by their identification number. The smaller their indentification number, the better their rank.
You have been given a list of all accepted submissions in the contest. You know the order that they were submitted, which contestant it was submitted by (), which problem it was submitted to (), and the rank of the contestant after their submission (). Unfortuntately, you have lost all incorrect submissions in the contest, as well as the specific times of the accepted submissions. Given this partial list of submission, can you recreate any scoreboard that is consistent with this list?
It is guaranteed that no contestant submitted an incorrect submission to a problem they already solved and that no two contestants had an accepted submission in the same minute. It is also guaranteed that a valid scoreboard can be recreated from the partial submission list.
For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [20%]
Subtask 4 [50%]
No additional constraints.
The first line contains integers, , , and , indicating that Zeyu's contest has contestants, problems, and accepted submissions.
The next lines describe the accepted submissions in the order that they were submitted. Each line contains integers, , , and , indicating that this submission was made by the contestant to the problem, and that they were rank after this submission. It is guaranteed that this list of accepted submissions was created from a valid scoreboard.
Output lines, describing any scoreboard that is consistent with the given list of accepted submissions. It is guaranteed that such a scoreboard exists. The scoreboard is listed in ascending order of the contestants' final rank.
The line should consist of strings in the following format:
- The first string should be an integer in the range representing the identification number of the contest who was rank at the end of the contest.
- The next strings describe the submissions the contestant made. The of these strings should be in the form
<time>is an integer in the range representing the time in minutes that the contestant submitted to the problem.
<penalty>is an integer in the range representing the number of incorrect submissions that the contestant made to the problem. If the contestant did not solve the problem, then the string should be
-/-instead of the format described. Note that all accepted submission times must be unique.
Note that for this problem, a verdict involving Presentation Error indicates that your output format is incorrect or the output does not represent a valid scoreboard, (including, but not limited to not outputting the contestants in the order of their final rank).
Sample Input 1
3 1 2 3 1 1 1 1 1
Sample Output 1
1 10/0 3 1/5 2 -/-
Sample Explanation 1
After the first accepted submission at minute, with incorrect submissions by contestant , they move to first place. After the second accepted submission at minutes, with incorrect submissions by contestant , they move to first place.
Sample Input 2
2 3 6 2 2 1 1 3 1 1 2 1 2 1 2 1 1 1 2 3 1
Sample Output 2
2 45/3 8/1 67/3 1 59/6 22/5 18/0
Sample Explanation 2
Note that after the first two submissions, there is a tie in the sum of submission times plus penalties. Since contestant has a smaller identification number, they are considered to be first place.