G. Dingding and His Favorite Finite Binary String
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

有一个长度为$$$n$$$的二进制字符串，我们将$$$k$$$个连续的字符分为一组，即第$$$1$$$个字符到第$$$k$$$个分为一组，第$$$k+1$$$个字符到第$$$2k$$$个字符为一组...保证$$$n$$$为$$$k$$$的倍数。你需要翻转（'0'变成'1','1'变成'0'）其中的一些字符，使得任意一组内的字符全部相等，在翻转次数最少的前提下，我们希望最终字符串被分成的'01'段的数量也最少。不仅如此，你还需要求出在满足前两个前提下，翻转的方案数有多少。

不同的翻转方案指的是翻转后的两个字符串在任何一个位置不同。

'01'段是指字符串以子段内全部字符相同为前提下最少划分的段数，例如'00100111'被划分成$$$4$$$个'01'段，'00000000'被划分成$$$1$$$个'01'段。

举个例子： 当$$$n=4,k=1$$$时，对于二进制字符串'0010'，最少需要翻转$$$0$$$次，最少分成的分成的'01'段的数量为$$$3$$$段，翻转方案数为$$$1$$$种。 当$$$n=8,k=4$$$时，对于二进制字符串'00110101'，最少需要翻转$$$4$$$次，最少分成的分成的'01'段的数量为$$$1$$$段，翻转方案为$$$2$$$种，即把字符串翻转为'00000000'或'11111111'，虽然把字符串翻转成'00001111'满足任意一组内的字符全部相等满足且翻转$$$4$$$次，但是此时字符串分成的分成的'01'段的数量为$$$2$$$段，**不满足**被分成的'01'段的数量也最少的条件，所以这不是一种合法的方案。

Input

第一行，一个整数 $$$t(1\le t \le 5·10^5)$$$，代表数据组数。

对于每组数据：

第一行，两个个整数 $$$n,k(1\le n \le 5·10^5;1\le k \le n)$$$，代表二进制字符串的长度与每组字符的字符数，满足$$$n$$$是$$$k$$$的倍数。

第二行是一个长度为$$$n$$$的二进制字符串。

保证 $$$\sum n \le 5·10^5$$$。

Output

对于每个二进制字符串，输出一行三个整数$$$a,b,c$$$，分别代表最少翻转次数、在保持最少翻转次数的前提下分成的'01'段的最少数量、在满足前两个前提下，翻转的方案数有多少。因为$$$a,b,c$$$可能较大，所以你输出答案时需要把三个数对于'998244353'取模。

Example
Input
3
4 1
0010
8 4
00110101
16 2
0100011000011011
Output
0 3 1
4 1 2
5 2 3
Note

对于样例的第$$$1$$$、$$$2$$$组数据的解释见题目描述。