CF1658F.Juju and Binary String

The cuteness of a binary string is the number of $\texttt{1}$s divided by the length of the string. For example, the cuteness of $\texttt{01101}$ is $\frac{3}{5}$.

Juju has a binary string $s$ of length $n$. She wants to choose some non-intersecting subsegments of $s$ such that their concatenation has length $m$ and it has the same cuteness as the string $s$.

More specifically, she wants to find two arrays $l$ and $r$ of equal length $k$ such that $1 \leq l_1 \leq r_1 \lt l_2 \leq r_2 \lt \ldots \lt l_k \leq r_k \leq n$, and also:

• $\sum\limits_{i=1}^k (r_i - l_i + 1) = m$;
• The cuteness of $s[l_1,r_1]+s[l_2,r_2]+\ldots+s[l_k,r_k]$ is equal to the cuteness of $s$, where $s[x, y]$ denotes the subsegment $s_x s_{x+1} \ldots s_y$, and $+$ denotes string concatenation.

Juju does not like splitting the string into many parts, so she also wants to minimize the value of $k$. Find the minimum value of $k$ such that there exist $l$ and $r$ that satisfy the constraints above or determine that it is impossible to find such $l$ and $r$ for any $k$.

一个二进制字符串的“可爱度”（cuteness）定义为其中字符 $\texttt{1}$ 的个数除以字符串长度。例如，$\texttt{01101}$ 的可爱度为 $\frac{3}{5}$。

Juju 有一个长度为 $n$ 的二进制字符串 $s$。她希望从中选出若干个互不相交的子段，使得这些子段拼接后总长度恰好为 $m$，且拼接所得字符串的可爱度与原字符串 $s$ 相同。

更准确地说，她希望找到两个长度均为 $k$ 的数组 $l$ 和 $r$，满足

$$1 \leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k \leq n,$$

且满足以下条件：

• $\sum\limits_{i=1}^k (r_i - l_i + 1) = m$；
• 字符串 $s[l_1,r_1]+s[l_2,r_2]+\ldots+s[l_k,r_k]$ 的可爱度等于 $s$ 的可爱度，其中 $s[x, y]$ 表示子段 $s_x s_{x+1} \ldots s_y$，而 $+$ 表示字符串拼接。

Juju 不喜欢将字符串分割成太多段，因此她还希望最小化 $k$ 的值。请找出满足上述约束的最小 $k$ 值；若对任意 $k$ 均不存在满足条件的 $l$ 和 $r$，则判定为不可能。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 2 \cdot 10^5$).

The second line of each test case contains a binary string $s$ of length $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq n \leq 2 \cdot 10^5$）。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, if there is no valid pair of $l$ and $r$, print $-1$.

Otherwise, print $k + 1$ lines.

In the first line, print a number $k$ ($1 \leq k \leq m$) — the minimum number of subsegments required.

Then print $k$ lines, the $i$-th should contain $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$) — the range of the $i$-th subsegment. Note that you should output the subsegments such that the inequality $l_1 \leq r_1 \lt l_2 \leq r_2 \lt \ldots \lt l_k \leq r_k$ is true.

对于每个测试用例，若不存在满足条件的 $l$ 和 $r$ 对，则输出 $-1$。

否则，输出 $k + 1$ 行。

第一行输出一个整数 $k$（$1 \leq k \leq m$），表示所需的最小子段数量。

随后输出 $k$ 行，第 $i$ 行应包含 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个子段的范围。注意：所输出的子段必须满足不等式 $l_1 \leq r_1 \lt l_2 \leq r_2 \lt \ldots \lt l_k \leq r_k$。

In the first example, the cuteness of $\texttt{0011}$ is the same as the cuteness of $\texttt{01}$.

In the second example, the cuteness of $\texttt{11000011}$ is $\frac{1}{2}$ and there is no subsegment of size $6$ with the same cuteness. So we must use $2$ disjoint subsegments $\texttt{10}$ and $\texttt{0011}$.

In the third example, there are $8$ ways to split the string such that $\sum\limits_{i=1}^k (r_i - l_i + 1) = 3$ but none of them has the same cuteness as $\texttt{0101}$.

In the last example, we don't have to split the string.

在第一个例子中，字符串 $\texttt{0011}$ 的“可爱度”与字符串 $\texttt{01}$ 的“可爱度”相同。

在第二个例子中，字符串 $\texttt{11000011}$ 的“可爱度”为 $\frac{1}{2}$，且不存在长度为 $6$ 的子段具有相同的“可爱度”。因此我们必须使用两个互不相交的子段 $\texttt{10}$ 和 $\texttt{0011}$。

在第三个例子中，共有 $8$ 种将字符串划分的方式使得 $\sum\limits_{i=1}^k (r_i - l_i + 1) = 3$，但其中没有任何一种划分方式所得各子段的“可爱度”均与 $\texttt{0101}$ 的“可爱度”相同。

在最后一个例子中，我们无需对字符串进行划分。