Problem 3. Sliding Window Summation

USACO 2026 First Contest, Silver

Bessie has a hidden binary string $b_1b_2\dots b_N$ ($1\le N\le 2\cdot 10^5$). The only information about $b$ you are given is a binary string $r_1r_2\dots r_{N-K+1}$ ($1 \le K \le 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 FORMAT (input arrives from the terminal / stdin):

There are $T$ ($1\le T\le 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\dots r_{N-K+1}$, where $r_i=\sum_{j=i}^{j+K-1}b_j\pmod{2}$.

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

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

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.

SCORING: Input 2: $N\le 8$Inputs 3-4: $K\le 8$ and the sum of $N$ over all tests does not exceed $10^4$.Inputs 5-11: No additional constraints.

Problem credits: Benjamin Qi