Задан массив из нулей и единиц \(a[0 \ldots n - 1] = [a_0, a_1, \ldots, a_{n - 1}]\). Обратите внимание, что в этой задаче, в отличие от остальных, индексы массива нумеруются с нуля, а не с единицы.
За один шаг массив \(a\) заменяется на другой массив длины \(n\) по следующим правилам:
- Сначала строится новый массив \(a^{\rightarrow d}\) — циклический сдвиг массива \(a\) вправо на \(d\) ячеек. Элементы этого массива определяются как \(a^{\rightarrow d}_i = a_{(i + n - d) \bmod n}\), где \((i + n - d) \bmod n\) — остаток от деления \(i + n - d\) на \(n\).
Таким образом весь массив \(a^{\rightarrow d}\) можно записать как \(\)a^{\rightarrow d} = [a_{n - d}, a_{n - d + 1}, \ldots, a_{n - 1}, a_0, a_1, \ldots, a_{n - d - 1}]\(\)
- Затем каждый элемент массива \(a_i\) заменяется на \(a_i \,\&\, a^{\rightarrow d}_i\), где \(\&\) — операция логического «И».
Например, если \(a = [0, 0, 1, 1]\) и \(d = 1\), то \(a^{\rightarrow d} = [1, 0, 0, 1]\), и значение \(a\) после первого шага будет равно \([0 \,\&\, 1, 0 \,\&\, 0, 1 \,\&\, 0, 1 \,\&\, 1]\), то есть \([0, 0, 0, 1]\).
Процесс завершается, когда массив перестает меняться. Для заданного массива \(a\) определите, будет ли он состоять из одних нулей по окончании процесса. Если да, то также найдите количество шагов, которое процесс совершит до своего завершения.
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите одно целое число — количество шагов, после которого массив впервые станет состоять из всех нулей. Если же после завершения процесса в массиве все еще будут присутствовать единицы, выведите -1.
Примечание
В третьем наборе входных данных из примера с массивом будут происходить следующие изменения:
- В начале \(a = [1, 1, 0, 1, 0]\), и \(a^{\rightarrow 2} = [1, 0, 1, 1, 0]\). Их поэлементное «И» равно \(\)[1 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 1, 0 \,\&\, 0] = [1, 0, 0, 1, 0]\(\)
- Теперь \(a = [1, 0, 0, 1, 0]\), тогда \(a^{\rightarrow 2} = [1, 0, 1, 0, 0]\). Их поэлементное «И» равно \(\)[1 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 0] = [1, 0, 0, 0, 0]\(\)
- И, наконец, при \(a = [1, 0, 0, 0, 0]\) получаем \(a^{\rightarrow 2} = [0, 0, 1, 0, 0]\). Их поэлементное «И» равно \(\)[1 \,\&\, 0, 0 \,\&\, 0, 0 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 0] = [0, 0, 0, 0, 0]\(\)
Таким образом, ответ —
\(3\) итерации.
В четвертом наборе входных данных массив не будет изменяться при сдвиге на \(2\) вправо, потому что каждый элемент будет вычисляться как \(0 \,\&\, 0\) или \(1 \,\&\, 1\). Таким образом, единицы останутся на своих местах, и ответ — -1, массив никогда не будет состоять только из нулей.