CF2255A.Hot Potatoes at the Fairy Warehouse

On a quiet afternoon at the Fairy Warehouse, Ithea gathers Chtholly, Nephren, and the other leprechauns for one last game before dinner: Hot Potatoes.

There are $2n$ leprechauns sitting in a circle, numbered from $1$ to $2n$ clockwise. They are divided into two teams: leprechauns with odd numbers belong to the Red Team, while those with even numbers belong to the Blue Team.

Initially, some leprechauns hold a potato. The game then lasts for $k$ rounds.

At the beginning of each round, both teams know the current positions of all potatoes. Then, simultaneously, every leprechaun holding a potato does exactly one of the following:

• Keep the potato, or
• Pass the potato to the next leprechaun clockwise, provided that the next leprechaun does not hold a potato at the beginning of the round.

If the next leprechaun holds a potato at the beginning of the round, the current holder must keep their potato. Whether a potato can be passed depends only on the positions of the potatoes at the beginning of the round.

Under these rules, every leprechaun holds at most one potato at any time.

When all $k$ rounds are over, the final bell rings. Every leprechaun still holding a potato is eliminated from the game. The score of each team is defined as the number of eliminated leprechauns on the other team. All members of each team cooperate and share all available information to maximize their team's score.

Find the scores of the Red Team and the Blue Team if both teams play optimally. It can be shown that the scores under optimal play are uniquely determined.

在一个安静的午后，妖精仓库里，伊瑟娅召集了克洛茜、奈芙伦以及其他小精灵们，在晚饭前进行最后一场游戏：热土豆。

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

初始时，部分小精灵手中持有一个土豆。随后游戏共进行 $k$ 轮。

每轮开始时，两支队伍均知晓当前所有土豆的位置。接着，所有手持土豆的小精灵同时执行以下操作之一：

• 保留手中的土豆；或
• 将土豆顺时针传递给下一位小精灵（即编号加 $1$，若当前编号为 $2n$ 则传给编号 $1$ 的小精灵），前提是该下一位小精灵在本轮开始时未持有土豆。

若下一位小精灵在本轮开始时已持有土豆，则当前持土豆者必须保留自己的土豆。能否传递土豆仅取决于本轮开始时各土豆的位置。

根据这些规则，任意时刻每个小精灵最多持有一个土豆。

当全部 $k$ 轮结束后，终场铃声响起。所有仍持有土豆的小精灵将被淘汰出游戏。每支队伍的得分定义为对方队伍中被淘汰的小精灵人数。每支队伍的所有成员协同合作，并共享所有可获得的信息，以最大化本队得分。

若双方均采取最优策略，求红队与蓝队各自的得分。可以证明，在双方最优策略下，双方得分是唯一确定的。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 10^5$, $1\le k\le 10^9$) — half the number of leprechauns and the number of rounds.

The second line contains a binary string $s$ of length $2n$ ($s_i=\texttt{0}$ or $\texttt{1}$) describing the initial state of the game. If $s_i=\texttt{1}$, leprechaun $i$ initially holds a potato; otherwise, they do not.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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=\texttt{0}$ 或 $\texttt{1}$），用于描述游戏的初始状态。若 $s_i=\texttt{1}$，则第 $i$ 个矮精灵初始时持有土豆；否则不持有。

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

For each test case, print two integers — the scores of the Red Team and the Blue Team, respectively, if they play optimally.

对于每个测试用例，输出两个整数——分别为红队和蓝队的得分（假设双方均采取最优策略）。

In the first test case, it is optimal for leprechaun $1$ to pass the potato to leprechaun $2$ in the only round. Afterwards, only leprechaun $2$, who belongs to the Blue Team, holds a potato. Therefore, the score of the Red Team is $1$, while the score of the Blue Team is $0$.

In the second test case, it is optimal for leprechaun $4$ to pass their potato to leprechaun $1$ in the only round. Note that leprechaun $3$ cannot pass their potato to leprechaun $4$, because leprechaun $4$ already holds a potato at the beginning of the round.

Here is a demonstration for the third test case:

Note that this is one possible optimal strategy for both teams. Other optimal strategies may exist, but the resulting scores are the same.

在第一个测试用例中，最优化的策略是：在唯一的一轮中，精灵 $1$ 将土豆传递给精灵 $2$。此后，仅有属于蓝队的精灵 $2$ 持有土豆。因此，红队得分为 $1$，而蓝队得分为 $0$。

在第二个测试用例中，最优化的策略是：在唯一的一轮中，精灵 $4$ 将其持有的土豆传递给精灵 $1$。注意，精灵 $3$ 无法将土豆传递给精灵 $4$，因为精灵 $4$ 在该轮开始时已持有土豆。

以下是第三个测试用例的演示：

注意，此方案仅为双方队伍的一种可能的最优策略。可能存在其他最优策略，但最终得分相同。