B. Коровки программируют
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Фермер Джон только что дал коровкам поиграться с программой! Программа содержит две целочисленные переменные 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.

Примеры
Входные данные
4
2 4 1
Выходные данные
3
6
8
Входные данные
3
1 2
Выходные данные
-1
-1
Примечание

В первом примере

  1. Для i = 1,  x изменяется следующим образом: , y становится 1 + 2 = 3.
  2. Для i = 2,  x изменяется следующим образом: , y становится 2 + 4 = 6.
  3. Для i = 3,  x изменяется следующим образом: , y становится 3 + 1 + 4 = 8.