Tokitsukaze and Meeting
Contest: Codeforces Round 789 (Div. 1)
Difficulty rating: 1700
Tags: data structures, implementation, math

Tokitsukaze is arranging a meeting. There are $$$n$$$ rows and $$$m$$$ columns of seats in the meeting hall.

There are exactly $$$n \cdot m$$$ students attending the meeting, including several naughty students and several serious students. The students are numerated from $$$1$$$ to $$$n\cdot m$$$. The students will enter the meeting hall in order. When the $$$i$$$-th student enters the meeting hall, he will sit in the $$$1$$$-st column of the $$$1$$$-st row, and the students who are already seated will move back one seat. Specifically, the student sitting in the $$$j$$$-th ($$$1\leq j \leq m-1$$$) column of the $$$i$$$-th row will move to the $$$(j+1)$$$-th column of the $$$i$$$-th row, and the student sitting in $$$m$$$-th column of the $$$i$$$-th row will move to the $$$1$$$-st column of the $$$(i+1)$$$-th row.

For example, there is a meeting hall with $$$2$$$ rows and $$$2$$$ columns of seats shown as below:

There will be $$$4$$$ students entering the meeting hall in order, represented as a binary string "1100", of which '0' represents naughty students and '1' represents serious students. The changes of seats in the meeting hall are as follows:

Denote a row or a column good if and only if there is at least one serious student in this row or column. Please predict the number of good rows and columns just after the $$$i$$$-th student enters the meeting hall, for all $$$i$$$.

Input format:
The first contains a single positive integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.

For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq n,m \leq 10^6$$$; $$$1 \leq n \cdot m \leq 10^6$$$), denoting there are $$$n$$$ rows and $$$m$$$ columns of seats in the meeting hall.

The second line contains a binary string $$$s$$$ of length $$$n \cdot m$$$, consisting only of zeros and ones. If $$$s_i$$$ equal to '0' represents the $$$i$$$-th student is a naughty student, and $$$s_i$$$ equal to '1' represents the $$$i$$$-th student is a serious student.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print a single line with $$$n \cdot m$$$ integers — the number of good rows and columns just after the $$$i$$$-th student enters the meeting hall.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first test case is shown in the statement.

After the $$$1$$$-st student enters the meeting hall, there are $$$2$$$ good rows and columns: the $$$1$$$-st row and the $$$1$$$-st column.

After the $$$2$$$-nd student enters the meeting hall, there are $$$3$$$ good rows and columns: the $$$1$$$-st row, the $$$1$$$-st column and the $$$2$$$-nd column.

After the $$$3$$$-rd student enters the meeting hall, the $$$4$$$ rows and columns are all good.

After the $$$4$$$-th student enters the meeting hall, there are $$$3$$$ good rows and columns: the $$$2$$$-nd row, the $$$1$$$-st column and the $$$2$$$-nd column.

Example input:
3
2 2
1100
4 2
11001101
2 4
11001101

Example output:
2 3 4 3
2 3 4 3 5 4 6 5
2 3 3 3 4 4 4 5

Editorial:
Obviously, we can calculate the answers of rows and columns separately.
For the answers of columns, we can observe that since there are only $$$n \cdot m$$$ students in total, no students will leave, and every time a new student entering the meeting hall, all columns will move one step to the right circularly, so the answer will not decrease. If the $$$i$$$-th student is a serious student, for all the previous students with subscript $$$j$$$ where $$$0 < j < i$$$, and $$$j \% m = i \% m$$$ are naughty students, the answer in the column will increase by $$$1$$$.
For the answer of rows, we can transfer it from the answer of $$$i-m$$$, which is equivalent to adding a new row to the answer of $$$i-m$$$. Suppose the last serious student is the $$$j$$$-th student. If $$$i-j<m$$$, the answer will increase by $$$1$$$, otherwise the answer will be the same as that of when the $$$i-m$$$ student enters the meeting hall.