На днях Вика изучала свой любимый интернет-ресурс — Википедию.
На просторах Википедии она вычитала про интересную математическую операцию побитового исключающего ИЛИ, обозначаемую \(\oplus\).
Вика стала изучать свойства этой загадочной операции. Для этого она взяла массив \(a\), состоящий из \(n\) целых неотрицательных чисел и применила одновременно ко всем его элементам следующую операцию: \(a_i = a_i \oplus a_{(i+1) \bmod n}\). Здесь \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\). Элементы массива нумеруются, начиная с \(0\).
Так как для полного изучения недостаточно проделать вышеописанные действия единожды, Вика повторяет их до тех пор, пока массив \(a\) не превратится в состоящий только из нулей.
Определите, через сколько описанных выше действий все элементы массива \(a\) станут нулевыми. Если такой момент никогда не наступит, выведите \(-1\).
Выходные данные
Выведите единственное число — минимальное число действий, необходимое, чтобы сделать все элементы массива \(a\) нулевыми, или \(-1\), если массив \(a\) никогда не станет нулевым.
Примечание
В первом примере после одной операции массив \(a\) станет равен \([3, 3, 3, 3]\). Через ещё одну операцию он будет равен \([0, 0, 0, 0]\).
Во втором примере массив \(a\) изначально состоит только из нулей.
В третьем примере после одной операции массив \(a\) станет равен \([0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 1 2
|
2
|
|
2
|
2
0 0
|
0
|
|
3
|
1
14
|
1
|
|
4
|
8
0 1 2 3 4 5 6 7
|
5
|