Zeyu is making his first ever Sadness Contest! His contest consists of ~M~ problems (numbered from ~1~ to ~M~) with ~N~ contestants participating (numbered from ~1~ to ~N~).

The rules of his contests are as follows:

• The contest lasts for ~10\,000\,000~ minutes.
• Each contestant may submit at most ~10\,000\,000~ 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 ~10~ minutes for each incorrect submission to a problem they solved. Note that there is no penalty for incorrect submissions to a 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 identification number, the better their rank.

You have been given a list of all ~K~ accepted submissions in the contest. You know the order that they were submitted, which contestant it was submitted by (~c_i~), which problem it was submitted to (~p_i~), and the rank of the contestant after their submission (~r_i~). Unfortunately, you have lost all incorrect submissions in the contest, as well as the specific times of the accepted submissions. Given this partial list of submissions, 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.

Constraints

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.

~1 \le N \le 200\,000~
~1 \le M \le 3~
~0 \le K \le N \cdot M~
~1 \le c_i \le N~
~1 \le p_i \le M~
~1 \le r_i \le N~

Subtask 1 [10%]

~1 \le N \le 2\,000~
~M = 1~

Subtask 2 [20%]

~1 \le N \le 2\,000~

Subtask 3 [20%]

~M = 1~

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains ~3~ integers, ~N~, ~M~, and ~K~, indicating that Zeyu's contest has ~N~ contestants, ~M~ problems, and ~K~ accepted submissions.

The next ~K~ lines describe the accepted submissions in the order that they were submitted. Each line contains ~3~ integers, ~c_i~, ~p_i~, and ~r_i~, indicating that this submission was made by the ~c_i^{th}~ contestant to the ~p_i^{th}~ problem, and that they were rank ~r_i~ after this submission. It is guaranteed that this list of accepted submissions was created from a valid scoreboard.

Output Specification

Output ~N~ 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 ~i^{th}~ line should consist of ~M + 1~ strings in the following format:

• The first string should be an integer ~a_i~ in the range ~[1, N]~ representing the identification number of the contest who was rank ~i~ at the end of the contest.
• The next ~M~ strings describe the submissions the ~a_i^{th}~ contestant made. The ~j^{th}~ of these strings should be in the form <time>/<penalty>. <time> is an integer in the range ~[1, 10\,000\,000]~ representing the time in minutes that the ~a_i^{th}~ contestant submitted to the ~j^{th}~ problem. <penalty> is an integer in the range ~[0, 9\,999\,999]~ representing the number of incorrect submissions that the ~a_i^{th}~ contestant made to the ~j^{th}~ problem. If the ~a_i^{th}~ contestant did not solve the ~j^{th}~ problem, then the ~j^{th}~ 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 ~1~ minute, with ~5~ incorrect submissions by contestant ~3~, they move to first place. After the second accepted submission at ~10~ minutes, with ~0~ incorrect submissions by contestant ~1~, 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 ~1~ has a smaller identification number, they are considered to be first place.