Juju and Binary String
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$.
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$.
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.
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.
Samples
4
4 2
0011
8 6
11000011
4 3
0101
5 5
11111
1
2 3
2
2 3
5 8
-1
1
1 5
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.