Seismic Design

Time limit1sMemory limit512 MB

Summary

Given a grid with one epicenter, barriers, and buildings, count how many buildings collapse under a main shock (range 2) and the aftershocks it causes (range 1).

Level: Medium4 of 10
Topics: Matrix, BFS, Simulation
Solved: No attempts yet

Problem

A magnitude 5.0 earthquake struck suddenly early this morning. The epicenter is one cell in a grid-shaped region of $N \times M$ cells. The earthquake from the epicenter is called the main shock, and the weaker quake caused by collapsing buildings is called an aftershock. The main shock spreads up, down, left, and right from the epicenter up to $2$ cells in each direction, and the aftershock spreads up, down, left, and right up to $1$ cell. Both the main shock and aftershocks affect buildings. A building without seismic design collapses as soon as the earthquake reaches it, but a building with seismic design collapses only after the earthquake reaches it $2$ times. When the main shock or an aftershock meets a seismic barrier or goes outside the grid, it stops spreading. The movement of the earthquake is shown in the figures below.



(1)	(2)

(3)	(4)

Input

The first line contains two integers $N$ ( $2 \leq N \leq 1\,000$ ) and $M$ ( $2 \leq M \leq 1\,000$ ), separated by a space.

From the second line, the next $N$ lines each contain a string of length $M$ . The string uses the following 5 characters, and there is exactly one epicenter.

@: epicenter
.: normal road
*: building without seismic design
#: building with seismic design
|: seismic barrier

Output

Print the number of collapsed buildings and the number of buildings that did not collapse, separated by a space, on one line.

Examples2

Example 1

Input

5 6
*.*...
..||..
..@*|*
.*.*..
..*##.

Expected output

4 5

Example 2

Input

7 9
...#...#.
.*.*..*..
...*..#..
...**.*..
.*..*.@..
.#...**..
..#.#..*.

Expected output

10 8