Các sinh viên phần mềm K1 đang phát triển website Online Classroom cho trường. Còn rất nhiều chức năng cần làm, em hãy giúp các bạn K1 hoàn thành chức năng: Tính điểm trung bình cho sinh viên khi biết điểm của các môn học.

Sắp đến ngày lễ tổng kết, phòng đào tạo muốn tìm một số sinh viên có điểm trung bình cao nhất ở mỗi khoa để trao học bổng. Tuy nhiên, hiện tại phòng đào tạo chỉ có một bảng điểm tổng hợp từ các khoa gồm các trường: MSSV, mã khoa, mã môn học và điểm. Do lễ tổng kết sắp đến gần nên phòng đào tạo muốn có một phần mềm để tìm ra ~k~ sinh viên để có điểm cao nhất mỗi khoa, hãy giúp phòng đào tạo viết chương trình này.

Input

• Dòng đầu tiên là số record điểm ~n (1 \leq n \leq 10^5)~
• ~n~ dòng tiếp theo gồm hai số nguyên là mã số sinh viên và mã môn học, số thứ ba là số thực (Double) là điểm của môn học.

Output

• Xuất ra danh sách sinh viên theo thứ tự điểm trung bình giảm dần, mỗi dòng gồm mã số sinh viên và điểm trung bình làm tròn đến chữ số thứ ~3~. Nếu hai sinh viên bằng điểm trung bình, xuất ra theo thứ tự tăng dần mã số sinh viên.

Example Input

12
1 1 5
1 2 7.5
2 1 8.0
2 2 7.0
3 1 10.0
4 2 7.0
4 3 4.5
3 2 3.0
5 1 6.5
5 2 4.5
6 1 10
6 2 5.5

Example Output

6 7.75
2 7.5
3 6.5
1 6.25
4 5.75
5 5.5