题目描述

农夫约翰给奶牛们一个程序玩，该程序包含两个整数变量 x 和 y，以及一个整数序列 \(a_1\), \(a_2\), …, \(a_n\)，执行以下步骤：
1. 开始时，x = 1，y = 0，如何在任何一步出现，x \(\leq\) 0 或者 x>n，则终止程序；
2. 将 x 和 y 同时增加 \(a_x\) 的值；
3. 将 y 增加 \(a_x\) 的值，x 减少 \(a_x\) 的值；
程序重复执行步骤 2 和步骤 3，直到程序终止（它有可能永远也不会终止）。奶牛们的算术不是很好，他们想看看程序是如何工作的，请帮助它们。
给出序列 \(a_2\), \(a_3\), …, \(a_n\)，对于每个 i（1 \(\leq\) i \(\leq\) n - 1 我们在序列 i, \(a_2\), \(a_3\), …, \(a_n\) 上跑一次程序，如果不能终止，输出 -1，否则输出 y 的终值。

输入格式

第一行一个整数 n；
接下来 n - 1 个整数 \(a_2\), \(a_3\), …, \(a_n\)。

输出格式

输出 n - 1 行，枚举 i 每次执行程序后的 y 值

样例1

输入

4
2 4 1

输出

3
6
8

样例2

输入

3
1 2

输出

-1
-1

数据范围

对于 30%的数据，2 \(\leq\) n \(\leq\) 10，1 \(\leq\) \(a_i\) \(\leq\) 10；
对于 100%的数据，2 \(\leq\) n \(\leq\) 2 \(\times\) \(10^5\)，1 \(\leq\) ai \(\leq\) \(10^9\)。

限制

1s

样例解释

样例 1：
1. i = 1，x 变化：1 -> 2 -> 0；y 变化：1 + 2 = 3；
2. i = 2，x 变化：1 -> 3 -> -1；y 变化：2 + 4 = 6；
3. i = 3，x 变化：1 -> 4 -> 3 -> 7；y 变化：3 + 1 + 4 = 8。

来源

Codeforces283B
CWOI新高二专题测试十四