Дан циклический массив \(a\) из \(n\) элементов, где \(n\) — нечетное. За одну операцию вы можете сделать следующее:
- Выберите индекс \(1 \le i \le n\) и увеличьте \(a_{i - 1}\) на \(1\), \(a_i\) на \(2\) и \(a_{i + 1}\) на \(1\). Элемент перед первым элементом является последним элементом, так как это циклический массив.
Циклический массив называется сбалансированным, если все его элементы равны между собой.
Найдите любую последовательность операций, чтобы сделать этот циклический массив сбалансированным, или определите, что это невозможно. Обратите внимание, что вам не нужно минимизировать количество операций.
Выходные данные
Для каждого набора входных данных:
- Если невозможно сделать циклический массив сбалансированным, выведите \(-1\).
- В противном случае выведите \(n\) целых чисел \(v_1, v_2, \ldots, v_n\) (\(0 \leq v_i \leq 10^{18}\)) — где \(v_i\) обозначает количество операций, примененных к индексу \(i\). Можно доказать, что если существует какое-то решение, то существует решение при данных ограничениях. Если существует несколько решений при данных ограничениях, выведите любое из них.
Примечание
В первом наборе входных данных:
- После \(1\) операции, примененной к индексу \(i = 2\), массив \(a = [3, 3, 3]\).
Во втором наборе входных данных:
- После \(2\) операций, примененных к индексу \(i = 1\), массив \(a = [5, 4, 5]\).
- После \(1\) операции, примененной к индексу \(i = 2\), массив \(a = [6, 6, 6]\).
В третьем наборе входных данных:
- После \(2\) операций, примененных к индексу \(i = 1\), массив \(a = [5, 4, 1, 2, 3]\).
- После \(3\) операций, примененных к индексу \(i = 3\), массив \(a = [5, 7, 7, 5, 3]\).
- После \(2\) операций, примененных к индексу \(i = 5\), массив \(a = [7, 7, 7, 7, 7]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
2 1 2
3
1 2 3
5
1 2 1 2 1
7
1 2 1 2 1 3 1
9
10000 10000 10000 10000 10000 10001 10002 10001 10000
1
10
|
0 1 0
2 1 0
2 0 3 0 2
4 2 7 0 8 0 6
1 1 1 1 1 1 0 1 1
0
|