EIU Programming Practices and Exams

Mr X ask his students to submit their exerices to a grading system. Students can submit unlimited times until the deadline for each problem. However, for each problem, student will received the highest score among all submissions. 

Given students submissions and the list of courses, help X to 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⁵, p ≤ 100, m ≤ 2*10⁵).

The second line contains n integers representing the student ids

The third line is p integers, which are the exercise codes.

In the next m lines, each line consists of 3 numbers: ni, pi and si, 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.

Example

Input:
2 2 3
1 2
11 12
1 11 80
1 12 90
2 12 100
Output:
1 85
2 50