Tokitsukaze and Meeting Codeforces Solution | Codeforces Problem Solution 2022

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$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$1$-st column of the 1$1$-st row, and the students who are already seated will move back one seat. Specifically, the student sitting in the 𝑗$j$-th (1≤𝑗≤𝑚−1$1\le j\le m-1$) column of the 𝑖$i$-th row will move to the (𝑗+1)$(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$1$-st column of the (𝑖+1)$(i+1)$-th row.

Solution Click Below:-  CLICK HERE

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

There will be 4$4$ students entering the meeting hall in order, represented as a binary string "1100", of which '0' represents naughty students and '1' 

Tokitsukaze and All Zero Sequence Codeforces Solution

[Solution] Tokitsukaze and Good 01-String

[Solution] Tokitsukaze and Good 01-String (hard version)

Tokitsukaze and Strange Inequality Codeforces Solution

Tokitsukaze and Meeting Codeforces Solution

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≤𝑡≤10000$1\le t\le 10000$) — the number of test cases.

For each test case, the first line contains two integers 𝑛$n$, 𝑚$m$ (1≤𝑛,𝑚≤106$1\le n,m\le {10}^6$; 1≤𝑛⋅𝑚≤106$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 106${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.

Join Now for Solution:-