403071: GYM100989 I Queue (B)

Amarneh likes Artificial Intelligence and always reads about intelligent techniques. As he was waiting in the line, he thought that there must be an intelligent way to re-order the students, such that there will always be enough change with the cashier.

Given the same input data as in the previous problem, can you help Amarneh find any order for serving the students in which the cashier will always have enough change to return to the students?

The first line of input contains a single integer N (1 ≤ N ≤ 10⁵), the number of students in the queue.

Each of the following N lines describes a student and contains 6 integers, K, F₁, F₂, F₃, F₄, and F₅, where K represents the amount of money the student has to pay, and F_i (0 ≤ F_i ≤ 100) represents the amount of the i^th type of money this student is going to give to the cashier.

It is guaranteed that no student will pay any extra notes. In other words, after removing any note from the set the student is going to give to the cashier, the amount of money will be less than what is required to buy the drink.

Print N integers on a single line that represents the order in which the students should line up, where the first integer represents the number of the student in the front of the queue. If such order doesn’t exist, print  - 1.

If there is more than one possible order, you can print any of them.

3
4 0 1 0 0 0
9 4 1 0 0 0
8 0 0 1 0 0

2 1 3 

1
40 0 0 0 0 1

-1