Juju and Binary String

1000ms

262144K

Description:

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 < l_2 \leq r_2 < \ldots < 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$$$.

Input:

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$$$.

Output:

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 < l_2 \leq r_2 < \ldots < l_k \leq r_k$$$ is true.

Sample Input:

Sample Output:

Note:

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.

Informação

Provedor Codeforces

Código CF1658F