B. Лягушка-путешественница
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лягушонок Горф отправился в путешествие по Болотному королевству. К несчастью, он не рассчитал длину своего прыжка и упал в колодец глубиной $$$n$$$ метров. Теперь Горф лежит на самом дне колодца и ему предстоит долгий путь наверх.

Стенки колодца в некоторых местах скользкие, а в некоторых, наоборот, очень удобные. А именно, если Горф сейчас находится на глубине $$$x$$$ метров от уровня земли, то за один прыжок он может подняться на любое расстояние от $$$0$$$ по $$$a_x$$$ метров вверх. (Заметим, что Горф не прыгает вниз, только вверх).

К сожалению, Горф не может прыгать без перерывов. После каждого прыжка ему нужно отдохнуть (даже после прыжка на $$$0$$$ метров). А потому, после прыжка в позицию $$$x$$$ метров ниже уровня земли, он соскользнет ровно на $$$b_x$$$ метров вниз (пока отдыхает).

Определите, за какое минимальное число прыжков Горф способен подняться до уровня земли.

Входные данные

В первой строке задано целое положительное число $$$n$$$ ($$$1 \le n \le 300\,000$$$) — глубина колодца.

Во второй строке задано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le i$$$), где $$$a_i$$$ — это максимальная высота, доступная для прыжка с глубины $$$i$$$.

В третьей строке вводится $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le n - i$$$), где $$$b_i$$$ — это глубина, на которую лягушонок провалится, взяв перерыв на глубине $$$i$$$.

Выходные данные

Если лягушонок не может выбраться из колодца, выведите $$$-1$$$. В противном случае сначала выведите целое число $$$k$$$ — минимально возможное количество прыжков.

Далее выведите последовательность глубин $$$d_1,\,d_2,\,\ldots,\,d_k$$$, где $$$d_j$$$ — это глубина, которую достигнет Горф после $$$j$$$-го прыжка, но до того, как соскользнет вниз во время передышки. Уровень земли считается равным $$$0$$$.

Если существует несколько решений, выведите любое из них.

Примеры
Входные данные
3
0 2 2
1 1 0
Выходные данные
2
1 0
Входные данные
2
1 1
1 0
Выходные данные
-1
Входные данные
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
Примечание

В первом примере Горф находится на дне колодца, за один прыжок вверх поднимается к отметке в $$$1$$$ метр глубины. После этого он соскальзывает вниз на метр и оказывается на отметке в $$$2$$$ метра. С этой отметки он уже сможет выпрыгнуть из колодца за один прыжок.

Во втором примере Горф может допрыгнуть до отметки в один метр, но сразу после этого соскользнет обратно на дно колодца, поэтому ему не выбраться.

В третьем примере выбраться из колодца можно только прыгнув с глубины $$$5$$$. Попасть напрямую туда нельзя, но можно добраться с помощью серии прыжков $$$10 \Rightarrow 9 \dashrightarrow 9 \Rightarrow 4 \dashrightarrow 5$$$, где $$$\Rightarrow$$$ обозначает прыжок вверх, а $$$\dashrightarrow$$$ обозначает спуск.