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\).
Выходные данные
Для каждого набора входных данных выведите в одной строке \(n \cdot m\) целых чисел — количество хороших рядов и столбцов сразу после того, как \(i\)-й студент войдет в конференц-зал.
Примечание
Первый набор входных данных показан в условии.
После того, как \(1\)-й студент входит в зал, остается \(2\) хороших ряда и столбца: \(1\)-й ряд и \(1\)-й столбец.
После того, как \(2\)-й студент входит в зал, остается \(3\) хороших ряда и столбца: \(1\)-й ряд, \(1\)-й столбец и \(2\)-й столбец.
После того, как \(3\)-й студент входит в зал, все \(4\) ряда и столбца хорошие.
После того, как \(4\)-й студент входит в зал, остается \(3\) хороших ряда и столбца: \(2\)-й ряд, \(1\)-й столбец и \(2\)-й столбец.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|