Sliding Window Summation

Bessie has a hidden binary string $b_{1} b_{2} \dots b_{N}$ ( $1 \leq N \leq 2 \cdot 1 0^{5}$ ). The only information about $b$ you are given is a binary string $r_{1} r_{2} \dots r_{N - K + 1}$ ( $1 \leq K \leq 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.

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 \leq 8$
Inputs 3-4: $K \leq 8$ and the sum of $N$ over all tests does not exceed $1 0^{4}$ .
Inputs 5-11: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

There are $T$ ( $1 \leq T \leq 1 0^{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} (mod 2)$ .

It is guaranteed that the sum of $N$ over all tests does not exceed $1 0^{6}$ .

Output Format

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

Submit

Language