K. Conan and Scoreboard
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Wow, what a contest! You helped Conan and his friends many times during this contest, and now it is time to give back.

Conan knows you have an exam directly after the contest. So, he decided to help the judges in calculating the results when the contest finish so they can announce it as soon as possible. Conan task is to find the name of students who will get the following awards:

  • First to Solve Problem x Award. This award is given to a student for being the first to solve a problem x in the contest.
  • Extreme Programmers Award. This award is given to the student who submitted the first correct solution in the contest.
  • Steadfast Gurus Award. This award is given to the student who submitted the last correct solution in the contest.
  • Solid Programmers Award. This award is given to the student who solved the maximum number of problems from the first attempt.
  • Relentless Programmers Award. This award is given to the student who made the largest number of incorrect submissions on a problem before solving it.

Conan shocked when he sees the submission's list due to its large size. So, Conan will need help to calculate the results. Of course, who can help Conan rather than you? Conan will give you the submission's list and you need to calculate the results for him. Remember you need to calculate the results as fast as possible because you do not want to miss your exam. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases.

The first line of each test case contains three integers n, m, and k (6 ≤ n, m ≤ 30) (1 ≤ k ≤ 10000), in which n is the number of problems in the contest, m is the number of students who participated in the contest, and k is the number of submissions. Problems are numbered from 1 to n, and students are numbered from 1 to m.

Then k lines follow, giving the details of the submissions. Each submission consists of three integers x, y and z, and a string t (1 ≤ x ≤ n) (1 ≤ y ≤ m) (), in which x is the problem's ID, y is the student's ID, z is 1 if the submission was correct and 0 otherwise. The time t is giving in the format mmm:ss, which means the submission was made mmm minutes and ss seconds after the start of the contest. Teams can start making submissions from 000:00, and no submission will be made after 299:59. No team will make a submission on a problem after solving it.

It is guaranteed that no two submissions were made at the same time. Also, it is guaranteed that at least one team solved at least one problem during the contest.

The sum of k overall test cases does not exceed 6 × 105.

Output

For each test case, print two lines. The first line must contain n integers in which the ith integers is the number of the first team to solve problem i or  - 1 if this problem has not been solved during the contest. The second line must contain four integers a, b, c, and d, in which a is the ID of the team who won the Extreme Programmers Award, b is the ID of the team who won the Steadfast Gurus Award, c is the ID of the team who won the Solid Programmers Award, and d is the ID of the team who won the Relentless Programmers Award.

If there is more than one team satisfying the condition of an award, this award will go to the team with the lowest ID.

Example
Input
1
6 6 13
1 1 1 005:23
1 4 1 007:49
1 5 1 008:21
1 2 1 010:32
3 1 0 012:18
3 1 1 013:20
1 6 1 016:20
1 3 1 018:46
2 3 0 029:14
2 3 1 037:14
5 1 0 042:37
2 2 1 044:35
5 1 1 055:29
Output
1 3 1 -1 1 -1
1 1 2 1