"Ну не гномы, а наказание какое-то!", – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь - другой уже проснулся! И так всю ночь.
У Белоснежки n гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать i-го гнома нужно a[i]
минут, и после этого он будет спать ровно b[i]
минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.
Например, пусть есть всего два гнома, a[1]
= 1, b[1]
= 10, a[2]
= 10, b[2]
= 20. Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.
Первая строка содержит число n (1 ≤ n ≤ 10^5
), вторая строка содержит числа a[1]
, a[2]
, ..., a[n]
, третья - числа b[1]
, b[2]
, ..., b[n]
(1 ≤ a[i]
, b[i]
≤ 10^9
).
Выведите n чисел - порядок, в котором нужно укладывать гномов спать. Если Белоснежке отдохнуть не удастся, выведите число -1.