题目描述

在妖精仓库的一个宁静下午，Ithea 把 Chtholly、Nephren 和其他小妖精们召集起来，在晚餐前玩最后一场游戏：烫手山芋。

有 $2n$ 个小妖精围坐成一个圈，顺时针方向依次编号为 $1$ 到 $2n$。他们被分成两队：编号为奇数的小妖精属于红队，编号为偶数的小妖精属于蓝队。

初始时，一些小妖精手里拿着一个土豆。游戏将持续进行 $k$ 个回合。

在每一轮开始时，两队都知道所有土豆的当前位置。然后，所有拿着土豆的小妖精同时执行以下操作之一：

• 保留手中的土豆
• 将土豆顺时针传给下一个小妖精，前提是该下一个小妖精在本轮开始时手里没有土豆。

如果下一个小妖精在本轮开始时手里有土豆，那么当前拿着土豆的小妖精必须保留土豆。一个土豆能否被传递，仅仅取决于本轮开始时所有土豆的位置状态。

在这些规则下，任何时候每个小妖精手里最多只能有一个土豆。

当 $k$ 个回合全部结束后，终场铃声响起。每一个手里仍拿着土豆的小妖精都会被淘汰出局。每个队伍的得分定义为对方队伍中被淘汰的小妖精数量。每个队伍的所有成员都会合作，并共享所有可用信息，以最大化自己队伍的得分。

如果两队都采取最优策略，请计算红队和蓝队的得分。可以证明，在双方都采取最优策略的情况下，两队的得分是唯一确定的。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$1 \le k \le 10^9$）—— 分别表示红/蓝队各自的人数（即总人数的一半）以及游戏的轮数。
• 第二行包含一个长度为 $2n$ 的二进制字符串 $s$（$s_i \in \{\text{'0'}, \text{'1'}\}$），描述游戏的初始状态。如果 $s_i = \text{'1'}$，表示小妖精 $i$ 初始时拿着一个土豆；否则表示没有。

输出格式

对于每个测试用例，输出一行两个整数，分别表示在双方都采取最优策略的情况下，红队的得分和蓝队的得分。中间用一个空格隔开。

样例输入 1

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

样例输出 1

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

说明

样例解释

• 在第一个测试用例中，对于红队来说，最优策略是在唯一的一轮中让小妖精 $1$ 将土豆传给小妖精 $2$。游戏结束后，只有属于蓝队的小妖精 $2$ 拿着土豆并被淘汰。因此，红队的得分为 $1$，而蓝队的得分为 $0$。
• 在第二个测试用例中，最优策略是在唯一的一轮中让小妖精 $4$ 将土豆传给小妖精 $1$。请注意，小妖精 $3$ 不能将土豆传给小妖精 $4$，因为在本轮开始时，小妖精 $4$ 手里已经有土豆了。
• 对于第三个测试用例，下面展示了一种可能的双方最优策略：

注意这只是双方最优策略之一，可能存在其他的最优操作，但最终的得分结果是相同的。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le n \le 10^5$，$1 \le k \le 10^9$。
• 保证 $s$ 是一个长度为 $2n$ 且仅由 0 和 1 组成的字符串。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $10^5$。
• 保证所有的输入数值均为整数。