← 返回题目列表

Codeforces · 1658/F

F. Juju 和二进制字符串

中文机器翻译题面 查看原题

二进制字符串的可爱度是 $$$\texttt{1}$$$ 的数量除以字符串的长度。例如,$$$\texttt{01101}$$$的可爱度是$$$\frac{3}{5}$$$。

Juju 有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。她想选择 $$$s$$$ 的一些不相交的子段,使得它们的串联长度为 $$$m$$$,并且与字符串 $$$s$$$ 具有相同的可爱度。

更具体地说,她想要找到两个长度相等的数组 $$$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$$$的最小值,使得存在满足上述约束的$$$l$$$和$$$r$$$,或者确定对于任何$$$k$$$不可能找到这样的$$$l$$$和$$$r$$$。

输入

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,如果没有有效的 $$$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 < l_2 \leq r_2 < \ldots < l_k \leq r_k$$$ 成立。

示例

输入 #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

注意

在第一个示例中,$$$\texttt{0011}$$$ 的可爱度与 $$$\texttt{01}$$$ 的可爱度相同。

在第二个示例中,$$$\texttt{11000011}$$$ 的可爱度是 $$$\frac{1}{2}$$$,并且没有大小为 $$$6$$$ 具有相同可爱度的子段。因此,我们必须使用 $$$2$$$ 不相交的子段 $$$\texttt{10}$$$ 和 $$$\texttt{0011}$$$。

在第三个示例中,有 $$$8$$$ 方法来分割字符串,使得 $$$\sum\limits_{i=1}^k (r_i - l_i + 1) = 3$$$ 但它们都没有 $$$\texttt{0101}$$$ 那样可爱。

在最后一个示例中,我们不必拆分字符串。