A8915 | Cow Program

Farmer John has just given the cows a program to play with! The program contains two integer variables, $x$ and $y$ , and performs the following operations on a sequence $a_{1},a_{2},...,a_{n}$ of positive integers:

1. Initially, $x=1$ and $y=0$ . If, after any step, $x<=0$ or $x>n$ , the program immediately terminates.
2. The program increases both $x$ and $y$ by a value equal to $a_{x}$ simultaneously.
3. The program now increases $y$ by $a_{x}$ while decreasing $x$ by $a_{x}$ .
4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on.

The cows are not very good at arithmetic though, and they want to see how the program works. Please help them!

You are given the sequence $a_{2},a_{3},...,a_{n}$ . Suppose for each $i$ $(1<=i<=n-1)$ we run the program on the sequence $i,a_{2},a_{3},...,a_{n}$ . For each such run output the final value of $y$ if the program terminates or -1 if it does not terminate.

The first line contains a single integer, $n$ ( $2<=n<=2·10^{5}$ ). The next line contains $n-1$ space separated integers, $a_{2},a_{3},...,a_{n}$ ( $1<=a_{i}<=10^{9}$ ).

Output $n-1$ lines. On the $i$ -th line, print the requested value when the program is run on the sequence $i,a_{2},a_{3},...a_{n}$ .

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.