B. Tokitsukaze и собрание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Tokitsukaze устраивает собрание. В зале собрания $$$n$$$ рядов и $$$m$$$ столбцов сидений.

На собрании присутствует ровно $$$n \cdot m$$$ студентов, в том числе несколько непослушных студентов и несколько серьезных студентов. Студенты нумеруются от $$$1$$$ до $$$n\cdot m$$$. Студенты входят в зал по порядку. Когда $$$i$$$-й студент войдет в зал, он сядет в $$$1$$$-й столбец $$$1$$$-го ряда, а уже сидящие студенты отодвинутся на одно место назад. В частности, студент, сидящий в $$$j$$$-м ($$$1\leq j \leq m-1$$$) столбце $$$i$$$-го ряда, переместится в $$$(j+1)$$$-й столбец $$$i$$$-го ряда, а ученик, сидящий в $$$m$$$-м столбце $$$i$$$-го ряда, переместится в $$$1$$$-й столбец $$$(i+1)$$$-го ряда.

Например, есть конференц-зал с $$$2$$$ рядами и $$$2$$$ столбцами мест, как показано ниже:

В зал войдут $$$4$$$ студента по порядку, представленному в виде двоичной строки «1100», из которых '0' представляет непослушных студентов, а '1' представляет серьезных. Порядок смены мест в зале собрания:

Обозначим ряд или столбец как хорошие тогда и только тогда, когда в этом ряду или столбце есть хотя бы один серьезный студент. Пожалуйста, предскажите количество хороших рядов и столбцов сразу после того, как $$$i$$$-й студент войдет в зал, для всех $$$i$$$.

Входные данные

Первая строка содержит единственное положительное целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных.

Для каждого набора входных данных в первой строке записаны два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n,m \leq 10^6$$$; $$$1 \leq n \cdot m \leq 10^6$$$), обозначающие наличие $$$n$$$ рядов и $$$m$$$ столбцов мест в зале.

Вторая строка содержит двоичную строку $$$s$$$ длины $$$n \cdot m$$$, состоящую только из нулей и единиц. Если $$$s_i$$$ равно '0', то $$$i$$$-й студент является непослушным, а если $$$s_i$$$ равно '1', то $$$i$$$-й студен является серьезным.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите в одной строке $$$n \cdot m$$$ целых чисел — количество хороших рядов и столбцов сразу после того, как $$$i$$$-й студент войдет в конференц-зал.

Пример
Входные данные
3
2 2
1100
4 2
11001101
2 4
11001101
Выходные данные
2 3 4 3
2 3 4 3 5 4 6 5
2 3 3 3 4 4 4 5
Примечание

Первый набор входных данных показан в условии.

После того, как $$$1$$$-й студент входит в зал, остается $$$2$$$ хороших ряда и столбца: $$$1$$$-й ряд и $$$1$$$-й столбец.

После того, как $$$2$$$-й студент входит в зал, остается $$$3$$$ хороших ряда и столбца: $$$1$$$-й ряд, $$$1$$$-й столбец и $$$2$$$-й столбец.

После того, как $$$3$$$-й студент входит в зал, все $$$4$$$ ряда и столбца хорошие.

После того, как $$$4$$$-й студент входит в зал, остается $$$3$$$ хороших ряда и столбца: $$$2$$$-й ряд, $$$1$$$-й столбец и $$$2$$$-й столбец.