Snow White and n gnomes
Snow White and n gnomes
"_Not gnomes, but some kind of punishment!_" - thought Snow White, once again trying to put the gnomes to sleep. You'll lay one to sleep - the other is already awake! And so all night.
The Snow White has n gnomes, and all of them are very different. She knows that in order to lay the i-th gnome to sleep, she needs ai
minutes, and after this he will sleep exactly bi
minutes. Help Snow White to find out if she can get at least a minute of rest, when all the gnomes are going to sleep, and if so, in what order does she need to put the gnomes to sleep.
For example, let there be only two gnomes, a1
= 1, b1
= 10, a2
= 10, b2
= 20. If Snow White first starts laying the first gnome, then it will take an 10 minutes to lay the second, and during this time the first will wake up. If she starts with the second gnome, then she will have time to lay the first one and will receive 10 minutes of rest.
Input
First line contains number n (1 ≤ n ≤ 105
), second line contains numbers a1
, a2
, ..., an
, third line contains numbers b1
, b2
, ..., bn
(1 ≤ ai
, bi
≤ 109
).
Output
Print n numbers - the order in which you need to put the gnomes to sleep. If Snow White does not have a rest, print the number -1.
2 1 10 10 20
2 1
2 10 10 10 10
-1