Zadanie

Fáranie

Počet bodov: 35

Marcelka si skracuje dni hraním jej obľúbenej hry Kopzhotovuj, známej svojim kockatým svetom.

Polovicu času kope, polovicu zhotovuje. Nielenže je kopanie nudnejšie, je aj nebezpečnejšie, lebo sa Marcelka vie stratiť. Po štvrtom blúdení sa rozhodla kopať len podľa stratégie vyvinutej skupinou KSP (Kopzhotovujskí Strategickí Plánovači), ktorá minimalizuje šancu zablúdenia.

Tá hovorí, že si máme zvoliť miesto na kopanie, a kopať smerom dole kým nenarazíme na spodok mapky. Počas kopania dole možno narazíme na kocku zlata. Ak hej, po jej vykopaní sa obzrieme doľava a doprava, či sme nenarazili na zlatú žilu (susediace kocky zlata). Ak áno, vykopeme ju (ale len na tejto úrovni - ak začneme kopať hore či dole, ľahšie sa stratíme). Keď všetky horizontálne susediace kocky zlata vykopeme, vrátime sa k našej šachte, a kopeme dodola ďalej s rovnakým postupom. Keď dosiahneme spodok mapky, vrátime sa na povrch.

Marcelkin kamarát Sabin získal svojimi hackerskými schopnosťami dáta o Marcelkinej mapke. Chcel by jej poradiť, kde má začať kopať, aby vykopala toľko zlata, koľko potrebuje (na postavenie zlatej sochy škrečka v nadživotnej veľkosti).

Z hackovania je však vyčerpaný, a preto potrebuje vašu pomoc.

Vstup

V prvom riadku vstupu sú čísla \(r\) a \(s\) - počet riadkov a stĺpcov úseku, o ktorom má Sabin dáta. Pod posledným riadkom je spodok mapky.

V každom z nasledujúcich \(r\) riadkov je \(s\) znakov, reprezentujúc horniny v danom úseku. Znak . reprezentuje kameň, znak # zlato.

V prvej sade platí \(1 \leq r,s \leq 100\). V druhej platí \(1 \leq r,s \leq 1500\).

Výstup

Vypíšte jeden riadok a v ňom \(s\) čísel - \(i\)-te z nich má byť počet kociek zlata, ktoré Marcelka vykope, ak si svoju šachtu spraví v \(i\)-tom stĺpci.

Príklad

Input:

5 6
#..#..
#####.
.###.#
.#.#..
..#...

Output:

6 9 9 10 5 1

Znakmi x vyznačíme, ktoré kocky by Marcelka vykopala z každého začiatočného stĺpca. Veľkými X vyznačíme, že to bola kocka zlata.

X..#.. #x.#.. #.x#.. #..X.. #..#x. #..#.x
XXXXX. XXXXX. XXXXX. XXXXX. XXXXX. #####x
x###.# .XXX.# .XXX.# .XXX.# .###x# .###.X
x#.#.. .X.#.. .#x#.. .#.X.. .#.#x. .#.#.x
x.#... .x#... ..X... ..#x.. ..#.x. ..#..x