[Solution] Juju and Binary String solution codeforces

Juju and Binary String solution codeforces – The cuteness of a binary string is the number of 𝟷1s divided by the length of the string. For example, the cuteness of 𝟶𝟷𝟷𝟶𝟷01101 is 3535.

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.

Juju and Binary String solution codeforces

More specifically, she wants to find two arrays 𝑙l and 𝑟r of equal length 𝑘k such that 1𝑙1𝑟1<𝑙2𝑟2<<𝑙𝑘𝑟𝑘𝑛1≤l1≤r1<l2≤r2<…<lk≤rk≤n, and also:

  • 𝑖=1𝑘(𝑟𝑖𝑙𝑖+1)=𝑚∑i=1k(ri−li+1)=m;
  • The cuteness of 𝑠[𝑙1,𝑟1]+𝑠[𝑙2,𝑟2]++𝑠[𝑙𝑘,𝑟𝑘]s[l1,r1]+s[l2,r2]+…+s[lk,rk] is equal to the cuteness of 𝑠s, where 𝑠[𝑥,𝑦]s[x,y] denotes the subsegment 𝑠𝑥𝑠𝑥+1𝑠𝑦sxsx+1…sy, 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.

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑚𝑛21051≤m≤n≤2⋅105).

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 21052⋅105.

Juju and Binary String solution codeforces

For each test case, if there is no valid pair of 𝑙l and 𝑟r, print 1−1.

Otherwise, print 𝑘+1k+1 lines.

In the first line, print a number 𝑘k (1𝑘𝑚1≤k≤m) — the minimum number of subsegments required.

Then print 𝑘k lines, the 𝑖i-th should contain 𝑙𝑖li and 𝑟𝑖ri (1𝑙𝑖𝑟𝑖𝑛1≤li≤ri≤n) — the range of the 𝑖i-th subsegment. Note that you should output the subsegments such that the inequality 𝑙1𝑟1<𝑙2𝑟2<<𝑙𝑘𝑟𝑘l1≤r1<l2≤r2<…<lk≤rk is true.

Example

input

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

Juju and Binary String solution codeforces

output

Copy
1
2 3
2
2 3
5 8
-1
1
1 5

Juju and Binary String solution codeforces

In the first example, the cuteness of 𝟶𝟶𝟷𝟷0011 is the same as the cuteness of 𝟶𝟷01.

In the second example, the cuteness of 𝟷𝟷𝟶𝟶𝟶𝟶𝟷𝟷11000011 is 1212 and there is no subsegment of size 66 with the same cuteness. So we must use 22 disjoint subsegments 𝟷𝟶10 and 𝟶𝟶𝟷𝟷0011.

In the third example, there are 88 ways to split the string such that 𝑖=1𝑘(𝑟𝑖𝑙𝑖+1)=3∑i=1k(ri−li+1)=3 but none of them has the same cuteness as 𝟶𝟷𝟶𝟷0101.

In the last example, we don’t have to split the string.

Leave a Comment