Фермер Джон только что дал коровкам поиграться с программой! Программа содержит две целочисленные переменные x и y. Ей подается на вход последовательность положительных целых чисел a1, a2, ..., an, в зависимости от которой она выполняет следующие операции:
- Изначально x = 1 и y = 0. Если после какого-то шага x ≤ 0 или x > n, то программа немедленно завершается.
- Программа одновременно увеличивает x и y на ax.
- Затем программа увеличивает y на ax, уменьшая x на ax.
- Программа попеременно выполняет шаги 2 и 3 (сначала 2, затем 3), пока не завершится (она может никогда не завершиться). Таким образом, последовательность шагов может начаться так: шаг 2, шаг 3, шаг 2, шаг 3, шаг 2 и так далее.
Коровки все же не очень хорошо считают, и поэтому они хотят разобраться, как работает программа. Пожалуйста, помоги им!
Дана последовательность a2, a3, ..., an. Предположим, что для каждого i (1 ≤ i ≤ n - 1) мы запускаем программу на последовательности i, a2, a3, ..., an. Для каждого такого запуска выведите итоговое значение y, если программа завершится, или -1, если программа не завершится.
Выходные данные
Выведите n - 1 строк. В i-ой строке выведите требуемое значение, когда программа запускается на последовательности i, a2, a3, ...an.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.