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

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

## 说明

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.