## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Tokitsukaze and Meeting Codeforces Solution | Codeforces Problem Solution 2022

D. Tokitsukaze and Meeting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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\le j\le m-1$) column of the $i$-th row will move to the $\left(j+1\right)$-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 $\left(i+1\right)$-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

[Solution] Tokitsukaze and Good 01-String

Tokitsukaze and Two Colorful Tapes Codeforces Solution

Tokitsukaze and Permutations Codeforces Solution

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

The first contains a single positive integer $t$ ($1\le t\le 10\phantom{\rule{thinmathspace}{0ex}}000$) — the number of test cases.

For each test case, the first line contains two integers $n$$m$ ($1\le n,m\le {10}^{6}$$1\le n\cdot m\le {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

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.