CF1677B.Tokitsukaze and Meeting

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$.

Tokitsukaze 正在组织一场会议。会议厅共有 $n$ 行 $m$ 列的座位。

恰好有 $n \cdot m$ 名学生参加本次会议，其中包括若干名淘气的学生和若干名认真的学生。学生编号从 $1$ 到 $n\cdot m$。学生们将按编号顺序依次进入会议厅。当第 $i$ 名学生进入会议厅时，他将坐在第 $1$ 行第 $1$ 列的位置，而已就座的学生则整体向后移动一个座位。具体而言：位于第 $i$ 行第 $j$ 列（其中 $1 \leq j \leq m-1$）的学生将移动至第 $i$ 行第 $(j+1)$ 列；而位于第 $i$ 行第 $m$ 列的学生将移动至第 $(i+1)$ 行第 $1$ 列。

例如，下图展示了一个 $2$ 行 $2$ 列的会议厅：

将有 $4$ 名学生按顺序进入会议厅，其类型用二进制字符串 "1100" 表示，其中 '0' 表示淘气的学生，'1' 表示认真的学生。会议厅座位的变化过程如下所示：

若某一行或某一列中至少存在一名认真的学生，则称该行（或该列）为“好”的。请预测：对每个 $i$，在第 $i$ 名学生进入会议厅之后，会议厅中“好”的行数与“好”的列数分别是多少。

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$.

第一行包含一个正整数 $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$ 列的座位。

第二行包含一个长度为 $n \cdot m$ 的二进制字符串 $s$，仅由字符 '0' 和 '1' 组成。若 $s_i$ 为 '0'，表示第 $i$ 个学生是调皮的学生；若 $s_i$ 为 '1'，表示第 $i$ 个学生是认真的学生。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

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.

对于每个测试用例，输出一行包含 $n \cdot m$ 个整数——即第 $i$ 个学生进入会议室后，此时“好”行与“好”列的数量。

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.

第一个测试用例已在题目描述中给出。

在第 $1$ 名学生进入会议室后，有 $2$ 个“好”的行和列：第 $1$ 行和第 $1$ 列。

在第 $2$ 名学生进入会议室后，有 $3$ 个“好”的行和列：第 $1$ 行、第 $1$ 列和第 $2$ 列。

在第 $3$ 名学生进入会议室后，全部 $4$ 行和 $4$ 列均为“好”的行和列。

在第 $4$ 名学生进入会议室后，有 $3$ 个“好”的行和列：第 $2$ 行、第 $1$ 列和第 $2$ 列。