28625번 - Спасительная загадка 다국어

문제

Загадочник похищает окружного прокурора Джила Колсона.

Чтобы спастись, Колсон должен отгадать три загадки. Бэтмен помогает ему отгадать первые две, но третья загадка оказалась слишком сложной. Сможете ли вы помочь ему с отгадкой?

Загадка устроена следующим образом:

1. Загадочник записал и спрятал массив целых чисел $a$ длины $n$.
2. Затем он циклически сдвинул его на какую-то величину $x$ влево, после чего полученный сдвиг поэлементно вычел из исходного массива.
3. Полученный в результате массив $$b = [a_1 - a_{x+1}, a_2 - a_{x+2}, \ldots, a_{n} - a_{x}]$$ (иными словами, массив, в котором $b_i = a_i - a_{(i + x) \bmod n}$ для всех $i$), Загадочник сообщил Колсону.

Требуется по данному массиву $b$ восстановить все возможные величины сдвига $x,ドル которые могли привести к получению такого массива $b$ из какого-то массива $a$.

입력

В первой строке ввода дано единственное целое число $n$ --- длина исходного массива (1ドル \leqslant n \leqslant 10^6$).

Во второй строке через пробел перечислены $n$ целых чисел $b_1,ドル $b_2,ドル \ldots, $b_n$ --- элементы полученного Загадочником массива $b$ ($|b_i| \leqslant 10^9$).

출력

Выведите через пробел $n - 1$ целое число, $i$-е из которых равно 1ドル,ドル если $x = i$ могло иметь место, и 0ドル$ иначе.

제한

노트

В первом примере такой массив $b$ мог быть получен, например, из массива $a = [2, 4, 4]$ сдвигом на 1ドル$ влево или из массива $a = [2, 2, 4]$ сдвигом на 2ドル$ влево.

В первом примере данный массив $b$ ни при каком $a$ не мог быть получен сдвигом на 3ドル,ドル а для сдвигов 1ドル$ или 4ドル,ドル например, подошли бы массивы $a = [1, 2, 0, 3, 7, 3]$ и $a = [3, 7, 0, 3, 4, 5],ドル соответственно.

Для третьего примера можно показать, что такой $b$ в принципе не мог быть получен описанным в условии образом.