题目描述

在精灵仓库一个安静的下午，Ithea召集了Chtholly、Nephren以及其他小精灵，在晚饭前玩最后一个游戏：烫手土豆。

有 $2n$ 个小精灵围成一圈，按顺时针编号为 $1$ 到 $2n$。他们分为两支队伍：编号为奇数的小精灵属于红队，编号为偶数的小精灵属于蓝队。

一开始，部分小精灵手里拿着土豆。游戏一共进行 $k$ 轮。

每一轮开始时，两支队伍都知道所有土豆当前所在的位置。随后，所有拿着土豆的小精灵会同时执行下面两种操作之一：

• 拿着土豆不动；
• 将土豆顺时针传给下一个小精灵，前提是该下一个小精灵在本轮开始时没有拿着土豆。

如果下一个小精灵在本轮开始时已经持有土豆，那么当前持有土豆的小精灵必须保留自己的土豆。土豆能否传递仅由本轮开始时刻各个土豆的位置决定。

在这套规则下，任意时刻每个小精灵手中至多有 $1$ 个土豆。

当全部 $k$ 轮结束后，终场铃声响起。所有仍然拿着土豆的小精灵会被淘汰。每支队伍的得分定义为对方队伍被淘汰的小精灵数量。同一支队伍的所有成员会互相配合，充分利用全部信息，让本队得分尽可能大。

假设双方都采取最优策略，求出红队与蓝队的得分。可以证明，双方最优策略下的得分是唯一确定的。

输入

每个测试点包含多组测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来给出各组测试用例。

每组测试用例第一行包含两个整数 $n$ 和 $k$（$1\le n\le 10^5$，$1\le k\le 10^9$），代表小精灵总数的一半以及游戏轮数。

第二行给出一个长度为 $2n$ 的 $01$ 字符串 $s$（$s_i=0$ 或 $s_i=1$），描述游戏初始状态。若 $s_i=1$，代表编号为 $i$ 的小精灵初始持有土豆；否则不持有。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出

对每组测试用例，输出两个整数，依次为双方均采取最优策略时红队得分、蓝队得分。

样例

6
2 1
1000
2 1
0011
3 2
101110
5 100000
1111111111
5 100000
0000000000
7 4
10011110101011

1 0
0 2
3 1
5 5
0 0
7 2

说明

第一组测试用例中，最优策略是小精灵 $1$ 在仅有的一轮中将土豆传给小精灵 $2$。结束后，只有属于蓝队的小精灵 $2$ 持有土豆。因此红队得分为 $1$，蓝队得分为 $0$。

第二组测试用例中，最优策略是小精灵 $4$ 在仅有的一轮中将土豆传给小精灵 $1$。注意小精灵 $3$ 不能把土豆传给小精灵 $4$，因为在本轮开始时小精灵 $4$ 已经拿着土豆。

第三组测试用例的演示图：

这只是双方的一组最优策略。可以存在其他最优策略，但最终得到的得分一定相同。

原题链接

原题链接