Algorithms and Data Structures

Sea Battle

notion image
You’re one of the developers of the Sea Battle game. Now you are responsible for updating one of the most important statistics in the game - given a board you should find out the number of healthy, dead, and wounded ships. You know that:
  • No ships share a side. So, if two neighbor cells in a grid are marked as part of a ship, then it’s the same ship.
  • In this game, the ships don’t necessarily form a straight line. This is an advanced mode of a game available for premium users.
  • If no bombs were dropped on a ship, then the ship is healthy.
  • If all the cells of the ship are bombed, then the ship is dead.
  • If only some cells are bombed, the ship is considered to be wounded.
You should write a program that given a grid of the current situation would print the number of healthy, dead, and wounded ships.

Input

The first line of the input contains two characters r and c (1 ≤ r, c ≤ 50) - rows and columns of the grid.
The next r rows contain c columns of characters representing the grid:
  • . represents water (no ship)
  • s represents a healthy ship cell
  • b represents a bombed ship cell

Output

The program should print 3 numbers - the number of healthy, dead, and wounded ships.

Examples

Input

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

3 1 2
 

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

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