Juju and Binary String

题意翻译

定义一个 01 串的可爱度为 $\frac{串中1的个数}{串长度}$。 现在有一个长度为 $n$ 的 01 串 $s$，要从中选取若干个不相交的子串，要求： - 所有子串长度加起来为 $m$。 - 所有子串拼起来后，可爱度和 $s$ 的可爱度一样。 现在要求你给出一个合法选取方案，并保证方案的子串**个数最少**。输出你的方案的子串个数，并输出每个子串的起始结束位置。 数据范围： - $t$ 组数据，$1\leq t\leq 10^4$。 - $1\leq m\leq n\leq 2\ ·10^5$。

题目描述

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.

输入输出样例

输入样例 #1

4
4 2
0011
8 6
11000011
4 3
0101
5 5
11111

输出样例 #1

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.