Page not loading? Try clicking here.
Placeholder

#8845
Subtask

Sliding Window Summation 1s 1024MB

Problems

Bessie has a hidden binary string b_1b_2…b_N (1≤N≤2⋅10^5). The only information about b you are given is a binary string r_1 r_2…r_{N−K+1} (1≤K≤N), where r_i is the remainder when the number of ones in the length-K window of b with leftmost index i is divided by two.

Output the minimum and maximum possible numbers of ones in Bessie's hidden binary string.


Input

There are T (1≤T≤10^3) independent test cases to be solved. Each test is specified by the following:

The first line contains N and K.

The second line contains the binary string r_1…r_{N−K+1}, where ri=∑^{j+K−1}_{j=i}bj(mod2).

It is guaranteed that the sum of N over all tests does not exceed 10^6.


Output

For each test case, output the minimum and maximum possible numbers of ones in Bessie's hidden binary string, separated by a single space.


Subtask

# Score Condition
#120

N \le 8

#230

K≤8 and the sum of N over all tests does not exceed 10^4

#350

No additional constraints.


Example 

7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000
3 3
2 3
1 4
0 4
1 5
1 3
0 5

For the first test case, K=1 means that r=b, and the number of ones in r is 3.

For the second test case, there are two possibilities for b: 10001 and 01110, having 2 and 3 ones, respectively.


Source

USACO 2026 First Contest, Silver

You must sign in to write code.