Một bệnh viện có ~N~ bệnh nhân đến khám bệnh rải rác trong ngày. Bệnh nhân thứ ~i~ có mã số ~ID_i~, đến viện lúc ~T_i~, cần ~D_i~ khoảng thời gian để bác sĩ khám xong, và có mức độ ưu tiên là ~P_i~ (số càng lớn, ưu tiên càng cao).

Bác sĩ chỉ có một người và bắt đầu làm việc từ thời điểm ~t = 0~. Tại bất kỳ thời điểm nào khi bác sĩ rảnh rỗi, bác sĩ sẽ gọi bệnh nhân đang chờ theo quy tắc sau:

1. Chọn người có mức độ ưu tiên ~P_i~ cao nhất.
2. Nếu có nhiều người cùng mức ưu tiên, chọn người đến viện sớm nhất (thời điểm ~T_i~ nhỏ nhất).
3. Nếu vẫn có nhiều người đến cùng lúc, chọn người có mã số ~ID_i~ nhỏ nhất.

Hãy in ra thứ tự mã số (~ID~) của các bệnh nhân lần lượt được bác sĩ khám.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
• ~N~ dòng tiếp theo, mỗi dòng chứa 4 số nguyên ~ID_i, T_i, D_i, P_i~ cách nhau bởi khoảng trắng. (~1 \le ID_i \le N~, ~0 \le T_i \le 10^9~, ~1 \le D_i \le 10^4~, ~1 \le P_i \le 100~).
• Dữ liệu đảm bảo các ~ID_i~ là phân biệt.

Kết quả

In ra một dòng duy nhất gồm ~N~ số nguyên là thứ tự ~ID~ của các bệnh nhân được khám, cách nhau bởi một khoảng trắng.

Ví dụ

Input

5
1 1 3 1
2 2 2 5
3 3 1 5
4 4 2 2
5 10 2 1

Output

1 2 3 4 5

Giải thích

• Thời điểm t=1: Bệnh nhân ID=1 đến. Bác sĩ rảnh ~\rightarrow~ Khám luôn. Khám xong lúc t = 1 + 3 = 4.
• Trong lúc bác sĩ khám người 1, những người ID=2, ID=3, ID=4 lần lượt đến và phải chờ.
• Thời điểm t=4: Bác sĩ khám xong người 1. Trong hàng đợi lúc này có ID=2, 3, 4.
  • Người 2 và 3 có ưu tiên cao nhất (~P=5~).
  • Người 2 đến sớm hơn (~T=2 < T=3~) ~\rightarrow~ Chọn khám người 2. Khám xong lúc t = 4 + 2 = 6.
• Thời điểm t=6: Hàng đợi có ID=3, 4. Khám người 3 (~P=5~). Xong lúc t=7.
• Thời điểm t=7: Hàng đợi có ID=4. Khám người 4. Xong lúc t=9.
• Thời điểm t=9: Bác sĩ rảnh, nhưng không có ai chờ.
• Thời điểm t=10: Bệnh nhân ID=5 đến. Bác sĩ khám luôn.
• Thứ tự gọi khám: 1 2 3 4 5.