样例下载

题目描述

老师在黑板上写了一个长度为 $N$ 的 01 字符串 $S$。

令 $S[i,j]$ 表示由 $S$ 中第 $i$ 个到第 $j$ 个字符构成的字符串。

对于 $S$ 的每个长度为 $L$ 的子串 $S[i,i+L-1]$ $(i=1,2,……, N-L+1)$，小明统计了其中含有字符 1 的个数是奇数个还是偶数个。小明将统计信息汇总成了一个字符串 $T$。具体地，$T$ 是一个长度为 $N-L+1$ 的 01 字符串，若 $T_i = 0$ 表示子串 $S[i, i+L-1]$ 含有偶数个 1，若 $T_i = 1$ 表示子串 $S[i, i+L-1]$ 含有奇数个 1。

后来不知道谁擦黑板把老师写的字符串擦掉了。

好在小明统计的信息还在。

现在请你根据小明的信息复原老师写的字符串。

你只需要计算出，老师写的字符串 $S$ 最少可能包含多少个 1，最多可能包含多少个 1。

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：两个整数 $N, L$。

• 第二行：一个长度为 $N-L+1$ 的 01 字符串 $T$。

输出格式

共 $T$ 行，每行两个整数，分别表示 $S$ 最少和最多可能包含的 1 的个数。

样例输入

3
3 1
101
4 4
0
5 2
1001

样例输出

2 2
0 4
2 3

数据范围

100% 的数据：$1 ≤ T ≤ 10^3$, $1 ≤ N ≤ 2·10^5$, $1 ≤ L ≤ N$, 数据保证所有组数据的 $\sum N ≤ 10^6$。其中

• 有 10% 的数据：$N ≤ 8$
• 另有 30% 的数据：$L ≤ 8$, 数据保证所有组数据的 $\sum N ≤ 10^4$。