CF1579F.Array Stabilization (AND version)

You are given an array $a[0 \ldots n - 1] = [a_0, a_1, \ldots, a_{n - 1}]$ of zeroes and ones only. Note that in this problem, unlike the others, the array indexes are numbered from zero, not from one.

In one step, the array $a$ is replaced by another array of length $n$ according to the following rules:

1. First, a new array $a^{\rightarrow d}$ is defined as a cyclic shift of the array $a$ to the right by $d$ cells. The elements of this array can be defined as $a^{\rightarrow d}_i = a_{(i + n - d) \bmod n}$, where $(i + n - d) \bmod n$ is the remainder of integer division of $i + n - d$ by $n$.

   It means that the whole array $a^{\rightarrow d}$ can be represented as a sequence $$a^{\rightarrow d} = [a_{n - d}, a_{n - d + 1}, \ldots, a_{n - 1}, a_0, a_1, \ldots, a_{n - d - 1}]$$

2. Then each element of the array $a_i$ is replaced by $a_i \,\&\, a^{\rightarrow d}_i$, where $\&$ is a logical "AND" operator.

For example, if $a = [0, 0, 1, 1]$ and $d = 1$, then $a^{\rightarrow d} = [1, 0, 0, 1]$ and the value of $a$ after the first step will be $[0 \,\&\, 1, 0 \,\&\, 0, 1 \,\&\, 0, 1 \,\&\, 1]$, that is $[0, 0, 0, 1]$.

The process ends when the array stops changing. For a given array $a$, determine whether it will consist of only zeros at the end of the process. If yes, also find the number of steps the process will take before it finishes.

你将得到一个仅由 0 和 1 构成的数组 $a[0 \ldots n - 1] = [a_0, a_1, \ldots, a_{n - 1}]$。注意，在本题中（与其他题目不同），数组下标从 0 开始编号，而非从 1 开始。

每一步操作中，数组 $a$ 将被替换为另一个长度为 $n$ 的数组，规则如下：

1. 首先，定义一个新数组 $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}]$$

2. 然后，将数组 $a$ 的每个元素 $a_i$ 替换为 $a_i \,\&\, a^{\rightarrow d}_i$，其中 $\&$ 是逻辑“与”（AND）运算符。

例如，若 $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$，请判断：最终数组是否将全部由 0 组成？若是，请进一步求出该过程在结束前共需多少步。

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The next $2t$ lines contain descriptions of the test cases.

The first line of each test case description contains two integers: $n$ ($1 \le n \le 10^6$) — array size and $d$ ($1 \le d \le n$) — cyclic shift offset. The second line of the description contains $n$ space-separated integers $a_i$ ($0 \le a_i \le 1$) — elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。

接下来的 $2t$ 行包含各测试用例的描述。

每个测试用例描述的第一行包含两个整数：$n$（$1 \le n \le 10^6$）—— 数组长度，以及 $d$（$1 \le d \le n$）—— 循环移位的偏移量。描述的第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 \le a_i \le 1$）—— 数组的元素。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the number of steps after which the array will contain only zeros for the first time. If there are still elements equal to $1$ in the array after the end of the process, print -1.

输出 $t$ 行，每行包含对应测试用例的答案。每个测试用例的答案应为一个整数——即数组首次全部变为零所需的步数。如果处理过程结束后数组中仍存在等于 $1$ 的元素，则输出 $-1$。

In the third sample test case the array will change as follows:

1. At the beginning $a = [1, 1, 0, 1, 0]$, and $a^{\rightarrow 2} = [1, 0, 1, 1, 0]$. Their element-by-element "AND" is equal to $$[1 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 1, 0 \,\&\, 0] = [1, 0, 0, 1, 0]$$
2. Now $a = [1, 0, 0, 1, 0]$, then $a^{\rightarrow 2} = [1, 0, 1, 0, 0]$. Their element-by-element "AND" equals to $$[1 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 0] = [1, 0, 0, 0, 0]$$
3. And finally, when $a = [1, 0, 0, 0, 0]$ we get $a^{\rightarrow 2} = [0, 0, 1, 0, 0]$. Their element-by-element "AND" equals to $$[1 \,\&\, 0, 0 \,\&\, 0, 0 \,\&\, 1, 0 \,\&\, 0, 0 \,\&\, 0] = [0, 0, 0, 0, 0]$$

Thus, the answer is $3$ steps.

In the fourth sample test case, the array will not change as it shifts by $2$ to the right, so each element will be calculated as $0 \,\&\, 0$ or $1 \,\&\, 1$ thus not changing its value. So the answer is -1, the array will never contain only zeros.

在第三个样例测试用例中，数组的变化过程如下：

1. 初始时 $a = [1, 1, 0, 1, 0]$，且 $a^{\rightarrow 2} = [1, 0, 1, 1, 0]$。它们按元素进行“与”（AND）运算的结果为

$$[1 \,\&\, 1, 1 \,\&\, 0, 0 \,\&\, 1, 1 \,\&\, 1, 0 \,\&\, 0] = [1, 0, 0, 1, 0]$$

2. 此时 $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]$$

3. 最后，当 $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$，即该数组永远不会全部变为零。