二进制字符串的可爱度是 $$$\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}$$$ 那样可爱。
在最后一个示例中,我们不必拆分字符串。