Морской бой

screen-22.webp

Вы являетесь одним из разработчиков игры Sea Battle. Ваша задача – обновить одну из самых важных игровых статистик: по заданному полю нужно определить количество кораблей в состояниях healthy, dead и wounded. Вам известно, что:

  • Ни один корабль не соприкасается с другим по стороне. Если две соседние клетки в сетке отмечены как часть корабля, значит они принадлежат одному и тому же кораблю.

  • В этой версии игры корабли не обязательно располагаются по прямой. Это усовершенствованный режим, доступный для премиум-пользователей.

  • Если в корабль не было ни одного попадания, он считается healthy.

  • Если все клетки корабля были подбиты, корабль считается dead.

  • Если была подбита лишь часть клеток, корабль считается wounded.

Вам нужно написать программу, которая, основываясь на текущем состоянии игрового поля, выводит количество healthy, dead и wounded кораблей.

Входные данные

Первая строка содержит два числа r и c (1 ≤ r, c ≤ 50) — количество строк и столбцов в сетке.

Следующие r строк содержат по c символов, описывающих поле:

  • . обозначает воду (отсутствие корабля)

  • s обозначает целую (неподбитую) клетку корабля

  • b обозначает подбитую клетку корабля

Выходные данные

Программа должна вывести 3 числа — количество кораблей в состояниях healthy, dead и wounded.

Примеры

Input

7 8
..s.bb.s
s.......
s.sssss.
b.s...s.
..sssbs.
s.......
ss......
Output

3 1 2

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue