Mr. Huy ask his students to submit their exercise to a grading system. Students can submit unlimited times until the deadline for each problem. However, for each problem, student will receive the highest score among all submissions. Note that, each exercise has a different weight.

Given students submissions and the list of courses, help Huy calculate grades for each student.

Input

• The first line contains three integers ~N, P, M,~ which are the number of students, the number of problems and the number of submissions ~(N ≤ 10^5, P ≤ 100, M ≤ 2*10^5)~.

• The second line contains ~N~ integers representing the student ids

• In the next ~P~ lines, each line consists of ~2~ numbers: ~P_i~ and Wi which are the exercise code and its weight.

• In the next ~M~ lines, each line consists of ~3~ numbers: ~N_i, P_i~ and ~S_i,~ which are student id, exercise code, and scores which show the results of each submission.

All numbers are in signed ~32~-bit integer ranges.

Output

• Consists of ~N~ lines, each containing a student ID and the average grade.

• The results should be in order of increasing student ids and the average grade is rounded down to the unit.

Sample Input

2 2 3
1 2
11 2
12 4
1 11 80
1 12 90
2 12 100

Sample Output

1 86
2 66