403071: GYM100989 I Queue (B)

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Queue (B) time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

Each of the following N lines describes a student and contains 6 integers, K, F1, F2, F3, F4, and F5, where K represents the amount of money the student has to pay, and Fi (0 ≤ Fi ≤ 100) represents the amount of the ith 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.

Output

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.

ExamplesInput
3
4 0 1 0 0 0
9 4 1 0 0 0
8 0 0 1 0 0
Output
2 1 3 
Input
1
40 0 0 0 0 1
Output
-1

加入题单

上一题 下一题 算法标签: