A. Горячая картошка на складе фей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В тихий полдень на складе фей Итея собирает Ктолли, Нефрен и других лепреконов для последней игры перед ужином — горячую картошку.

$$$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$$$) — половина количества лепреконов и количество раундов.

Вторая строка содержит бинарную строку $$$s$$$ длины $$$2n$$$ ($$$s_i=\texttt{0}$$$ или $$$\texttt{1}$$$), описывающую начальное состояние игры. Если $$$s_i=\texttt{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$$$ уже держит картошку в начале раунда.

Ниже приведена иллюстрация для третьего набора входных данных:

Обратите внимание, что это одна из возможных оптимальных стратегий для обеих команд. Могут существовать и другие оптимальные стратегии, но итоговые результаты будут одинаковыми.