Cho danh sách bệnh nhân tại một bệnh viện. Mỗi bệnh nhân có thông tin gồm:

• Mã bệnh nhân
• Họ và tên
• Khoa điều trị
• Số ngày nằm viện
• Chi phí mỗi ngày

Hãy sắp xếp danh sách bệnh nhân theo thứ tự giảm dần của tổng chi phí điều trị. Nếu có nhiều bệnh nhân có cùng tổng chi phí, ưu tiên bệnh nhân có mã bệnh nhân nhỏ hơn. Biết rằng: tổng chi phí điều trị = số ngày nằm viện × chi phí mỗi ngày.

Yêu cầu: Sinh viên sử dụng struct để lưu thông tin.

Input

• Dòng đầu tiên ghi số nguyên ~n~ (~1 \leq n \leq 1000~) là số lượng bệnh nhân.

• ~n~ dòng tiếp theo, mỗi dòng ghi 5 thông tin: số nguyên ~m~ là mã bệnh nhân; chuỗi ký tự ~s_1~ là họ tên bệnh nhân (viết liền, dùng dấu gạch dưới nếu cần); chuỗi ký tự ~s_2~ là tên khoa điều trị; số nguyên ~d~ là số ngày nằm viện; số nguyên ~c~ là chi phí mỗi ngày. Các thông tin cách nhau bởi dấu cách.

Output

• ~n~ dòng, mỗi dòng ghi thông tin của một bệnh nhân đã được sắp xếp theo thứ tự giảm dần của tổng chi phí điều trị, và tăng dần theo mã bệnh nhân nếu tổng chi phí bằng nhau. Mỗi dòng ghi: mã bệnh nhân ~m~, họ tên ~s_1~, khoa điều trị ~s_2~, tổng chi phí điều trị. Các thông tin cách nhau bởi dấu cách.

Ví dụ:

Input

5  
1001 Nguyen_Van_Hoa Noi_Tong_Hop 10 350000  
1002 Le_Thi_Thu_Trang Nhi 7 450000  
1003 Pham_Van_Nam Ngoai_Khoa 5 700000  
1004 Tran_Thi_Hanh Tim_Mach 12 300000  
1005 Do_Hoai_Bac Da_Lieu 15 200000  

Output

1004 Tran_Thi_Hanh Tim_Mach 3600000
1001 Nguyen_Van_Hoa Noi_Tong_Hop 3500000
1003 Pham_Van_Nam Ngoai_Khoa 3500000
1002 Le_Thi_Thu_Trang Nhi 3150000
1005 Do_Hoai_Bac Da_Lieu 3000000