Дождь всё не желал прекращаться, как и моя проклятая жизнь. Моей целью был Дракон — разбойник и убийца, получивший своё прозвище за то, что в одиночку сжёг целый город вместе со всеми жителями. Добрый Волшебник оставался моей последней зацепкой. Вряд ли он что-то знал, но выбирать не приходилось.
После краха экономики Добрый Волшебник отошёл от дел и устроился работать сторожем на Центральном Кладбище. Когда-то главный советник Короля теперь копал могилы и вытирал пыль с холодных могильных плит. Я шёл, увязая по голень в зыбкой кладбищенской земле, словно зовущей меня остаться. И наконец я увидел Доброго Волшебника, изучающего карту кладбища.
Я сказал, что ищу Дракона, на что он ответил, что в этом случае мне бы следовало забронировать себе клочок земли на его кладбище. Я бы улыбнулся в ответ, если бы помнил, как это делается. Он сказал, что занят решением очень важной задачи, и не может отвлечься.
Кладбище представляло собой клетчатое поле размером n × m клеток. Под одну могилу в зависимости от размера гроба отводился прямоугольник шириной в одну клетку, а длиной в несколько. В Сказочном Королевстве живёт много разных существ, так что длина гроба могла быть самой разной. Добрый Волшебник для каждой длины могилы хотел вычислить, сколько существует различных способов выделить землю под такую могилу на его кладбище, учитывая, что некоторые клетки уже могут быть заняты могилами. Старик явно был не в своём уме, но я решил помочь ему, чтобы скорее перейти к делу.
В первой строке записаны два целых числа через пробел: n и m (1 ≤ n, m ≤ 105, n × m ≤ 106) — размеры кладбища в клетках.
Далее в n строках записано по m символов — карта кладбища. В i-й строке на j-й позиции записан символ «.», если соответствующая клетка свободна и может быть использована под могилу, либо символ «+», если соответствующая клетка занята.
Выведите
целых чисел через пробел. На k-ой позиции выведите, сколько существует различных способов выкопать могилу длиной k клеток.
3 4
...+
.+.+
+++.
6 4 1 0
4 3
...
.+.
.+.
...
10 10 6 2
| Название |
|---|


