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: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

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