Most Ordered Way

Interview

Time limit0.3sMemory limit1024 MB

Summary

Order N tasks with times T and deadlines D so each finishes on time, choosing the lexicographically smallest order, or print * if impossible.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Sofia was given $N$ assignments from school, numbered from 1 to $N$ . Each assignment has two values, $T$ and $D$ . $T$ is the number of minutes needed to finish it, and $D$ is its deadline, meaning it must be completed no later than $D$ minutes from now.

Sofia can do the assignments in any order, one at a time. Once she starts an assignment, she keeps working on it until it is done. She spends all her time on the assignments. She can start right away, and after finishing one assignment she starts the next immediately, without breaks.

Sofia is a perfectionist and wants to finish every assignment. She first planned to do them in the given order, but she soon realized that this could make some of them miss their deadlines. If several orders finish every assignment on time, she wants the most ordered one. Write a program that tells her how to organize her work.

Time limit: 300 ms. Memory limit: 1024 MB.

Input

The first line contains an integer $N$ ( $1 \le N \le 5000$ ). Each of the next $N$ lines contains two integers $T$ and $D$ ( $1 \le T \le D \le 10^9$ ).

Output

Output a single line with a permutation of the integers from 1 to $N$ describing an order in which the assignments can be done so that each is completed on time. If no such order exists, output * (asterisk). If more than one permutation works, output the lexicographically smallest one.

Examples4

Example 1
Input
```
2
5 9
5 9
```
Expected output
```
*
```
Example 2
Input
```
3
6 6
2 9
2 1000
```
Expected output
```
1 2 3
```
Example 3
Input
```
3
6 6
2 1000
2 9
```
Expected output
```
1 3 2
```
Example 4
Input
```
3
30 100
20 100
10 100
```
Expected output
```
1 2 3
```