青蛙峡谷正在沼泽王国旅行。不幸的是,在一次失败的跳跃之后,他掉进了一口深$$$n$$$米的井里。现在戈尔夫在井底,向上还有很长的路要走。
井壁的表面质量各不相同:有些地方很滑,但有些地方有方便的壁架。换句话说,如果戈尔夫位于地面以下 $$$x$$$ 米处,那么他一次跳跃就可以上升从 $$$0$$$ 到 $$$a_x$$$ 米(含)的任意整数距离。 (请注意,戈尔夫不能跳下,只能跳上)。
不幸的是,戈尔夫每次跳跃后都必须休息一下(包括跳 $$$0$$$ 米)。在跳到地面以下 $$$x$$$ 米的位置后,他在休息时会向下滑落 $$$b_x$$$ 米。
计算 Gorf 到达地面所需的最小跳跃次数。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$) — 井的深度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le i$$$),其中 $$$a_i$$$ 是 Gorf 可以从地面以下 $$$i$$$ 米跳跃的最大高度。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le n - i$$$),其中 $$$b_i$$$ 是 Gorf 在地面以下 $$$i$$$ 米处休息时滑落的距离。
输出
如果 Gorf 无法到达地面,则打印 $$$-1$$$。否则,首先打印整数 $$$k$$$ — 最小可能的跳转次数。
然后打印序列 $$$d_1,\,d_2,\,\ldots,\,d_k$$$,其中 $$$d_j$$$ 是 Gorf 在第 $$$j$$$ 次跳跃之后、但在休息期间滑落之前将达到的深度。地面水平等于 $$$0$$$。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 0 2 2 1 1 0
输出 #1
2 1 0
输入 #2
2 1 1 1 0
输出 #2
-1
输入 #3
10 0 1 2 3 5 5 6 7 8 5 9 8 7 1 5 4 3 2 0 0
输出 #3
3 9 4 0
注意
在第一个示例中,Gorf 在井底并跳到地面以下 $$$1$$$ 米的高度。之后,他滑落一米,停留在距地面 $$$2$$$ 米的高度。现在,从这里开始,他可以一跳到达地面。
在第二个示例中,Gorf 可以跳到地面以下一米,但会滑回井底。这就是为什么他无法到达地面。
在第三个示例中,Gorf 只能从地面以下 $$$5$$$ 米的高度到达地面。 Gorf 可以通过一系列跳跃 $$$10 \Rightarrow 9 \dashrightarrow 9 \Rightarrow 4 \dashrightarrow 5$$$ 达到这个高度,其中 $$$\Rightarrow$$$ 是跳跃,$$$\dashrightarrow$$$ 在休息期间滑动。