Sofia 有 $N$ 项学校布置的作业，编号从 $1$ 到 $N$。对于每项作业，她都知道两个值 $T$（耗时）和 $D$（截止日期），表示完成该作业需要 $T$ 分钟，且必须在从现在起 $D$ 分钟内完成。

Sofia 可以按任意顺序完成作业，她一次只能做一项作业，一旦开始某项作业，她会一直工作直到该作业完成。Sofia 只会花费时间做作业。这意味着她可以立即开始工作，并且每次完成一项作业后，她都可以立即开始下一项，中间没有任何休息（真是勤奋，对吧？）。

Sofia 是个完美主义者，她想完成所有的作业。最初，她想按照给定的顺序完成作业，但她很快意识到这种限制可能会导致作业无法按时完成。因此，如果存在多种在截止日期前完成所有作业的方法，Sofia 希望以“最有序”的方式完成它们。你能告诉她如何安排工作吗？时间紧迫，她现在就需要你的建议。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 5000$)，表示作业的数量。 接下来的 $N$ 行，每行描述一项作业，包含两个整数 $T$ 和 $D$ ($1 \le T \le D \le 10^9$)，表示完成该作业需要 $T$ 分钟，且必须在从现在起 $D$ 分钟内完成。

输出格式

输出一行，包含一个 $1$ 到 $N$ 的排列，描述了可以按时完成所有作业的顺序；如果不存在这样的顺序，则输出字符 “*”（星号）。如果存在多个可以按时完成作业的排列，请输出字典序最小的那个。

样例

样例输入 1

2
5 9
5 9

样例输出 1

*

样例输入 2

3
6 6
2 9
2 1000

样例输出 2

1 2 3

样例输入 3

3
6 6
2 1000
2 9

样例输出 3

1 3 2

样例输入 4

3
30 100
20 100
10 100

样例输出 4

1 2 3