Problem B: The Right Job

In the likely event that your team will rank among the first at MIUP 2012, very soon you will be contacted by the big international software companies, all eager to draw on your programming talent. Some will offer a bigger salary, others a fantastic working environment, a challenging project, the opportunity to work with a new technology, or the prospect of a brilliant international career. You will be at a loss, not knowing which offer to accept, fearing to take the wrong decision.

Fear no more! Being a programming person, just write a program to decide for you. May we suggest the Analytical Hierarchy Process, AHP for short? We’ll explain it with an example, which actually can apply to you.

Suppose that after some soul-searching, you have found that you pursue four objectives for your first job as a software developer: a large salary (obj₁), a challenging project (obj₂), a high quality of living in the city to where you will be relocated (obj₃), and a lot of traveling (obj₄).

Not all these objectives are worth the same, for you. For example, in your opinion, a high salary is twice as important as a challenging project and four times as important as a lot of traveling.

You can write down a matrix a, where a_ij means that for you, objective i is a_ij times more important than objective j. In this matrix, a_ii = 1 and a_ij × a_ji = 1, of course.

Next, you normalize the matrix, by dividing each value by the sum of its column. Then you compute the weight of each objective as the sum of each line divided by the number of columns. Easy?

Now suppose you got offers from IBM (job₁), in Zurich, from Microsoft (job₂), in London, and from Google (job₃) in Mountain View. In your perspective, job₁ is twice as important in terms of salary as job₃ and four times as important as job₂, and job₃ is six times as important in terms of salary as job₂:

Repeating the same steps for the other 3 objectives, normalizing the 4 matrices and calculating the weights, we get the preferences of the jobs in respect to the objectives:

The estimation of the preferences of each job in respect to each objective (the weight) is given by the average of the a_i,j, j=1,..,3 of the normalized matrix.

Finally, to compute the combined scores of each job, you must add the product of the objective weight and preference. For example, the score of job₁ is given by:

score(job₁) = 0.5222 × 0.4166 + 0.2364 × 0.3854 + 0.1524 × 0.1317 + 0.2014 × 0.0663.

Task

Your task is to write a program that given the objectives and their relative worth and the job offers, and you appreciation of their relative value for each objective, ranks the job offers using the AHP method.

Input

The first line contains two integers, N and M, separated by a single space, indicating respectively the number of objectives and number of jobs.

The second line contains a positive integer P that indicates how many pairwise objectives comparison will follow, followed by P lines with 3 integers in the form “A B I”, indicating that objective A is more important I times than objective B. The value of the missing pair comparisons is 1. The pairs can come in any order and the same pair of objectives cannot appear multiple times.

Then come exactly N groups of pairwise jobs comparisons, one for each of the objectives. The i-th group corresponds to objective i. The input format is the same as the pairwise objectives comparison.

Output

The output file consists of a single line (including the newline character) displaying the number of the M jobs ordered by descending score, and separated by single spaces. You can be assured that there will never be ties in the combined scores of two different jobs.

Constraints

Input example

4 3
6
1 2 2
1 3 3
1 4 4
2 3 5
2 4 7
3 4 3
3
1 2 4
1 3 2
3 2 6
3
1 2 5
3 1 4
3 2 9
2
2 1 4
2 3 7
3
1 3 2
2 1 4
2 3 5
 

Output example

3 1 2

MIUP'2012, 20 de Outubro, DCC/FCUP

This document was translated from L^AT_EX by H^EV^EA.