Mali Perica je rešio da obiđe Srbiju i posebno je zainteresovan za obilazak vodopada širom zemlje. Kada je bio na Gostiljskim vodopadima, pokušao je da proceni tok vode na dnu vodopada.

Kao što svi znamo, vodopad ima visinu ~h~ metara i širinu ~n~ metara. Vodopad je takođe sa leve i desne strane ograničen ivicama tako da voda nikada ne otiče levo i desno od njegovih granica. Još jedna zanimljiva stvar je što vodopad može imati stene koje će preusmeravati tok vode. Naime, ako vertikalni mlaz vode naiđe na stenu, sav njen tok se deli na dva dela tako da jedan deo otiče na desno a drugi na levo. Ukoliko se stena nalazi uz levu ili desnu granicu vodopada, tada se sav tok vode preusmerava na jednu stranu. Više stena se može nalaziti jedna pored druge i u tom slučaju se voda preusmerava samo na kraj i početak celog niza stena. Garantuje se da će u svakoj visini vodopada postojati bar jedno mesto koje nema stenu tako da je vodi garantovan prolaz na dole.

Formalno, vodopad možemo predstaviti binarnom matricom ~h \times n~, u kojoj je svako polje ili prohodno ili se tu nalazi stena. Redovi se indeksiraju počevši od 1, tako da je prvi red na vrhu matrice, a ~h~-ti red na dnu. Protok vode ima vrednost 1 na vrhu svake kolone. Voda se u svakoj koloni spušta niz matricu, sve dok ne naiđe na stenu. Ukoliko naiđe na stenu, sav protok se deli na dva celobrojna dela i polovina ide na levu stranu a druga polovina na desnu stranu. Ukoliko je protok neparan, tada preostala jedinica ide levo ili desno po sledećem pravilu:

• ukoliko je red neparan, jedinica viška ide levo

• ukoliko je red paran, jedinica viška ide desno

Ako se više uzastopnih nula nalazi u redu matrice (više uzastopnih stena), tada se ukupan protok iznad bloka uzastopnih nula deli na dva dela i jedna polovina preusmerava na prvo mesto levo od bloka a druga na desno. Pravilo za preostalu jedinicu protoka je isto kao i malopre - ako je red neparan višak ide levo od bloka, a ako je paran desno. Ako se stena ili blok stena nalazi uz levu ili desnu ivicu matrice, sav protok iznad stene ili bloka se usmerava na suprotnu stranu. Garantovano je da neće postojati red matrice koji sadrži samo nule.

Perica vam je dao matricu koja predstavljaja izgled jednog vodopada. Vaš zadatak je da odredite protok vode na svim mestima na njegovom dnu.

Opis ulaza

U prvom redu standardnog ulaza nalaze se dva broja ~h~ i ~n~, koji predstavljaju visinu i širinu matrice, respektivno. U svakom od narednih ~h~ redova nalazi se po ~n~ brojeva iz skupa ~\{0, 1\}~, pri čemu ~0~ označava da se na odgovarajućem polju nalazi stena, dok ~1~ predstavlja prohodno polje.

Opis izlaza

U jedinom redu standardnog izlaza potrebno je ispisati ~n~ brojeva - vrednost toka na dnu svake od kolona matrice.

Primer 1

Ulaz

3 3
1 1 0
1 0 1
0 1 1

Izlaz

0 2 1

Primer 2

Ulaz

3 3
0 1 0
1 0 1
1 1 0

Izlaz

1 2 0

Primer 3

Ulaz

4 5
1 0 1 0 1
1 1 0 0 1
0 1 1 1 0
1 0 1 0 1

Izlaz

1 0 3 0 1

Primer 4

Ulaz

5 7
1 1 1 1 0 0 0
1 0 1 0 1 0 1
1 1 0 0 0 1 0
1 0 0 1 1 0 1
0 1 1 0 1 1 0

Izlaz

0 2 1 0 2 2 0

Primer 5

Ulaz

1 3
1 0 1

Izlaz

2 0 1

Objašnjenje primera

U prvom primeru, posle prvog reda, protoci imaju vrednosti ~[1, 2, 0]~, jer se voda iz treće kolone preusmerava na levo zbog toga što je tu stena uz desnu ivicu. Nakon drugog reda, protoci su ~[2, 0, 1]~, jer se dve jedinice protoka iz srednje kolone dele na dva dela. Konačno, protok na kraju trećeg reda je ~[0, 2, 1]~, jer se tok uz ivicu preusmerava na suprotnu stranu.

U drugom primeru, protoci na kraju redova su:

0 3 0
1 0 2
1 2 0

U trećem primeru protoci na kraju redova su:

2 0 2 0 1
2 1 0 0 2
0 3 0 2 0
1 0 3 0 1

U četvrtom primeru, protoci na kraju redova su:

1 1 1 4 0 0 0
1 0 4 0 2 0 0
1 3 0 0 0 3 0
2 0 0 2 1 0 2
0 2 1 0 2 2 0

U petom primeru postoji samo jedan red, na čijoj se sredini nalazi stena. Pošto je u pitanju neparan red, tok iz sredine se preusmerava na levo.

Ograničenja

• ~1 \leq n,h~
• ~n \cdot h \le 10^6~

Test primeri su podeljeni u 5 disjunktnih grupa:

• U test primerima vrednim ~20~ poena: ~n \le 10~, ~h \le 10~.
• U test primerima vrednim ~20~ poena: ~h \le 10~.
• U test primerima vrednim ~20~ poena: ~n \le 100~.
• U test primerima vrednim ~20~ poena: ni u jednoj vrsti nema uzastopnih nula.
• U test primerima vrednim ~20~ poena: nema dodatnih ograničenja.