Giải bài trực tuyến

Today RomanD3 wants to race his old bicycle to Do Son beach with two friends of his, on his way he thought out a problem named "A Dwarf - N Snow Whites":

On his hard way to Do Son beach, he races with N Snow White racing on N different bicycles, but none of them wants to go alone. Given that the i^th Snow White wants to be taken by the dwarf RomanD3 for T_i minute(s), then she can go alone for (only) D_i minute(s) (she will cry after that); RomanD3 wants to "escape" from them soon to go... by bus with the N+1^th Snow White on the bus (whom he likes), so he must take each Snow White exactly one time but not let any of them cry; then he needs at least one minute to go with his lady (in dream ;)) ).

Please help him to determine whether he can do or not.

Input

- The first line contains number N.
- Next N line(s), the i^th line contains two numbers T_i, D_i.

Output

- Print out -1 whether he can not "escape" from them or print out the order of serving them before he can jump on the bus ;))

Example

Input:
2
2 11
11 30

Output:
2 1

Limitations

- n ≤ 10⁵.