农夫约翰刚刚给奶牛们提供了一个可以玩的程序!该程序包含两个整数变量 x 和 y,并对正整数序列 a1, a2, ..., an 执行以下操作:
1. 最初,x = 1且y = 0。如果在任何步骤之后x ≤ 0或x > n,则程序立即终止。
2. 程序将 x 和 y 同时增加等于 ax 的值。
3. 程序现在将 y 增加 ax,同时将 x 减少 ax。
4. 程序重复执行步骤 2 和 3(首先是步骤 2,然后是步骤 3),直到终止(可能永远不会终止)。因此,执行步骤的顺序可以从:步骤2、步骤3、步骤2、步骤3、步骤2等开始。
虽然奶牛不太擅长算术,但它们想看看程序是如何工作的。请帮助他们!
给定序列 a2, a3, ..., an。假设对于每个 i (1 ≤ i ≤ n - 1),我们在序列 i, a2, a3, ..., an 上运行程序。对于每次这样的运行,如果程序终止,则输出 y 的最终值;如果程序未终止,则输出 -1。
输入
第一行包含一个整数 n (2 ≤ n ≤ 2·105)。下一行包含 n - 1 个空格分隔的整数 a2, a3, ..., an (1 ≤ ai ≤ 109)。
输出
输出 n - 1 行。在第 i 行,打印程序在序列 i、a2、a3、...an 上运行时请求的值。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 2 4 1
输出 #1
3 6 8
输入 #2
3 1 2
输出 #2
-1 -1
注意
在第一个样本中
1. 对于 i = 1, x 变为 $$1 \rightarrow 2 \rightarrow 0$$,y 变为 1 + 2 = 3。
2. 对于 i = 2, x 变为 $$1 \rightarrow 3 \rightarrow - 1$$,y 变为 2 + 4 = 6。
3. 对于 i = 3, x 变为 $$1 \rightarrow 4 \rightarrow 3 \rightarrow 7$$,y 变为 3 + 1 + 4 = 8。