John quyết định xem một vài bộ phim kinh dị vào tối nay. Có bộ phim, đánh số từ đến . Phim thứ có độ dài và một cảnh kinh dị xuất hiện duy nhất sau khi bộ phim chiếu được phút.
Tuy nhiên, John thường có thói quen ngủ quên trong khi xem phim. Thói quen này được mô tả bằng một giá trị là “độ sợ”, ban đầu giá trị này là . Mỗi phút xem phim sẽ làm độ sợ giảm xuống đơn vị với tốc độ giảm không đổi (ví dụ, sau giây, độ sợ bị giảm ). Khi độ sợ giảm xuống dưới , John sẽ ngủ quên và không thể xem được những cảnh phim còn lại (kể cả trong trường hợp có những cảnh kinh dị phía sau). Để bù lại, mỗi cảnh kinh dị trong phim sẽ ngay lập tức làm tăng độ sợ của John thêm đơn vị và giúp cậu có đủ sức xem phim.
John muốn chọn thứ tự xem phim sao cho cậu có thể xem được trọn vẹn nhiều bộ phim nhất. Nếu có nhiều phương án như vậy, thứ tự từ điển của các bộ phim cần xem là nhỏ nhất. Giúp John xác định thứ tự xem phim cần thiết.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương là số bộ phim;
dòng sau, mỗi dòng chứa hai số nguyên và .
Dữ liệu ra:
Đưa ra dòng là thứ tự xem các bộ phim trong phương án tối ưu;
Ví dụ:
Dữ liệu vào:
2
100 1
50 49
Dữ liệu ra:
1
0
Dữ liệu vào:
4
100 77
100 76
100 75
100 74
Dữ liệu ra:
3
0
1
2
Giải thích:
Ở test thứ hai, John cần xem bộ phim trước để đảm bảo có thể xem được trọn vẹn một bộ phim. Không có cách nào cho kết quả tôt hơn, nên thứ tự là thứ tự từ điển nhỏ nhất cần tìm.
