Вам задан массив \(a\), состоящий из \(n\) целых чисел. За один ход вы можете прыгнуть с позиции \(i\) в позицию \(i - a_i\) (если \(1 \le i - a_i\)) или в позицию \(i + a_i\) (если \(i + a_i \le n\)).
Для каждой позиции \(i\) от \(1\) до \(n\) вы хотите узнать минимальное количество ходов, необходимое, чтобы достичь любой позиции \(j\) такой, что \(a_j\) имеет четность, отличающуюся от четности \(a_i\) (то есть если \(a_i\) нечетно, то \(a_j\) должно быть четным и наоборот).
Выходные данные
Выведите \(n\) целых чисел \(d_1, d_2, \dots, d_n\), где \(d_i\) равно минимальному количеству ходов, необходимому, чтобы достичь любой позиции \(j\) такой, что \(a_j\) имеет четность, отличающуюся от четности \(a_i\) (то есть если \(a_i\) нечетно, то \(a_j\) должно быть четным и наоборот) или же -1, если такой позиции достичь невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
4 5 7 6 7 5 4 4 6 4
|
1 1 1 2 -1 1 1 3 1 1
|