Farmer John always wanted a good map of his farm, so he purchased a satellite photograph of his land which is represented by $R$ ($1 \le R \le 75$) rows and $C$ ($1 \le C \le 75$) columns in the photo. One part of a photo looks something like this:
..................
..#####.......##..
..#####......##...
..................
#.......###.....#.
#.....#####.......In trying to interpret the photo, he figures that every connected shape is either a barn or a cow. A "connected shape" is a set of one or more #'s that are adjacent to each other either vertically or horizontally. The following would be two distinct "connected shapes":
....
.#..
..#.
....FJ claims that a connected shape is a barn if it is a filled-in rectangle whose four sides are parallel to the x and y axes. In the first photo above, there are three barns (sizes $2\times1$, $2\times5$, and $1\times1$) and two cows (you'd be surprised at the size of some of FJ's cows!). Count the number of barns and cows in his satellite photo.
A cow never completely encircles another cow or barn.
Input
- Line 1: Two space-separated integers: $R$ and $C$.
- Lines $2$ through $R+1$: Line $i+1$ represents row $i$ of the photograph and contains $C$ characters (and no spaces).
Output
- Line 1: The number of barns in the photo.
- Line 2: The number of cows in the photo.
Examples
Input 1
5 8
#####..#
#####.##
......#.
.###...#
.###..##Output 1
2
2Input Details
The photo consists of 5 lines, each of which is 8 characters long.
Output Details
The photo has 2 barns (the shapes on the left) and 2 cows (on the right).
Problem credits: Brian Dean, 2004