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₁,a₂,...,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₂,a₃,...,a_n. Suppose for each i (1≤i≤n-1) we run the program on the sequence i,a₂,a₃,...,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⁵). The next line contains n-1 space separated integers, a₂,a₃,...,a_n (1≤a_i≤10⁹).

Output n-1 lines. On the i-th line, print the requested value when the program is run on the sequence i,a₂,a₃,...a_n.

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