EIU Programming Practices and Exams

Trong một số môn học, giảng viên muốn khuyến thích sinh viên rèn luyện kỹ năng lập trình nên sẽ cộng điểm cho các bạn sinh viên giải được bài trên trang Codeforces trong giờ thi. Tuy nhiên, các bài trên trang codeforces có độ khó khác nhau nên số điểm cộng cho các bài là khác nhau. Cụ thể, với mỗi kì thi, điểm cộng từng bài sẽ được tính sau như sau:

Giảng viên đã yêu cầu sinh viên cung cấp tên tài khoản làm bài trên trang codeforces (mỗi sinh viên chỉ có 1 tài khoản), và đã có danh sách các bài nộp đúng của các tài khoản này trên codeforces (dữ liệu không bị trùng lắp). Hãy viết chương trình tính điểm cộng của các sinh viên.

Input

Dòng đầu tiên là số sinh viên n và số bài nộp đúng m (n ≤ 10⁵, m ≤ 10⁵).

n dòng tiếp theo, mỗi dòng gồm 1 số nguyên r và một chuỗi s là mã số sinh viên và tài khoản codeforces (r có 10 chữ số, chuỗi s có không quá 20 ký tự).

m dòng tiếp theo, mỗi dòng gồm số nguyên c là mã kì thi, tên tài khoản và bài đã làm thể hiện thông tin của 1 bài nộp đúng trên codeforces. (1 ≤ c ≤ 10000).

Output

Với mỗi sinh viên, xuất ra thông tin gồm mã sinh viên, tên tài khoản, số điểm cộng trên 1 dòng. Các thông tin cách nhau 1 khoảng trắng. Danh sách được sắp xếp theo thứ tự ưu tiên điểm cộng giảm dần, mã số sinh viên tăng dần.

Example

Input:
3 5
1500001000 nguyenvana
1500123455 tranvanb
1401111188 nguyenthic
1 nguyenvana A
2 tranvanb B
1 tranvanb C
1 nguyenthic A
3 nguyenthic D


Output:
1401111188 nguyenthic 13
1500123455 tranvanb 13
1500001000 nguyenvana 3