Лягушонок Горф отправился в путешествие по Болотному королевству. К несчастью, он не рассчитал длину своего прыжка и упал в колодец глубиной \(n\) метров. Теперь Горф лежит на самом дне колодца и ему предстоит долгий путь наверх.
Стенки колодца в некоторых местах скользкие, а в некоторых, наоборот, очень удобные. А именно, если Горф сейчас находится на глубине \(x\) метров от уровня земли, то за один прыжок он может подняться на любое расстояние от \(0\) по \(a_x\) метров вверх. (Заметим, что Горф не прыгает вниз, только вверх).
К сожалению, Горф не может прыгать без перерывов. После каждого прыжка ему нужно отдохнуть (даже после прыжка на \(0\) метров). А потому, после прыжка в позицию \(x\) метров ниже уровня земли, он соскользнет ровно на \(b_x\) метров вниз (пока отдыхает).
Определите, за какое минимальное число прыжков Горф способен подняться до уровня земли.
Выходные данные
Если лягушонок не может выбраться из колодца, выведите \(-1\). В противном случае сначала выведите целое число \(k\) — минимально возможное количество прыжков.
Далее выведите последовательность глубин \(d_1,\,d_2,\,\ldots,\,d_k\), где \(d_j\) — это глубина, которую достигнет Горф после \(j\)-го прыжка, но до того, как соскользнет вниз во время передышки. Уровень земли считается равным \(0\).
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере Горф находится на дне колодца, за один прыжок вверх поднимается к отметке в \(1\) метр глубины. После этого он соскальзывает вниз на метр и оказывается на отметке в \(2\) метра. С этой отметки он уже сможет выпрыгнуть из колодца за один прыжок.
Во втором примере Горф может допрыгнуть до отметки в один метр, но сразу после этого соскользнет обратно на дно колодца, поэтому ему не выбраться.
В третьем примере выбраться из колодца можно только прыгнув с глубины \(5\). Попасть напрямую туда нельзя, но можно добраться с помощью серии прыжков \(10 \Rightarrow 9 \dashrightarrow 9 \Rightarrow 4 \dashrightarrow 5\), где \(\Rightarrow\) обозначает прыжок вверх, а \(\dashrightarrow\) обозначает спуск.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 2 2
1 1 0
|
2
1 0
|
|
2
|
2
1 1
1 0
|
-1
|
|
3
|
10
0 1 2 3 5 5 6 7 8 5
9 8 7 1 5 4 3 2 0 0
|
3
9 4 0
|