CSES - Rakennus II
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevi aikoo rakentaa metsään suorakulmion muotoisen talon. Metsässä voi kuitenkin olla puita, eikä talo saa mennä minkään puun päälle.

Tehtäväsi on laskea jokaiselle mahdolliselle talon koolle a \times b, montako mahdollista näin suurta tonttia on olemassa.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut n ja m, jotka määrittävät metsän koon.

Tämän jälkeen syötteessä on metsän kuvaus. Jokainen ruutu on tyhjä (.) tai puu (*).

Tuloste

Tulosta n riviä, joista kullakin on m lukua: halutut tonttien määrät.

Rajat

  • 1 \le n,m \le 1000

Esimerkki

Syöte:

4 7
...*.*.
.*.....
.......
......*

Tuloste:

24 17 13 9 6 3 1 
16 9 7 5 3 1 0 
9 3 2 1 0 0 0 
3 0 0 0 0 0 0

Selitys: Esimerkiksi mahdollisia 2 \times 4 -kokoisia tontteja on 5 kpl.