404685: GYM101608 I Counting Votes

I. Counting Votestime limit per test1.5 secondsmemory limit per test256 megabytesinputvotes.inoutputstandard output

The organizers of the ACM Movie Night event decided to hold a voting to let members choose one of the available three movies. Each member can pick an ink-stamp of the first letter of the movie he/she wants to vote for {‘H’, ‘M’, or ‘Y’}, and use it on a big whiteboard rotated in any angle they want, but without overlapping/touching previous votes or touching the borders of the whiteboard.

Stamps for each movie are available in different sizes but they are all made of the same font, and all of them will leave a black mark on the whiteboard. The picture shows the used font and how the whiteboard may look at the end of the voting process (it represents an actual test case but scaled down).

Given an image that represents the whiteboard, help the ACM know the number of votes for each movie.Input

The first line of input contains a single integer T (1 ≤ T ≤ 32), the number of test cases.

The first line of each test case contains two space-separated integers r and c (r, c ≤ 1000), the number of rows and columns of the image, respectively.

Each of the following r lines contains c characters that are either ‘.’ (a white pixel), or ‘#’ (a black pixel).

It is guaranteed that the input is valid and matches the following constraints:

• All cells on the border are white.
• The image contains at least one letter.
• The width of any used letter before rotating it is at least 20 pixels.
• Each maximal connected component of black pixels represents one of the three letters.

The total number of pixels in all test cases doesn't exceed 5 × 10⁶.

Output

For each test case, print a single line with three space-separated integers, the number of times each of ‘H’, ‘M’, and ‘Y’ appears on the whiteboard, respectively.

Note

A connected component is a set of black pixels such that it is possible to start at any pixel from the set and reach all other pixels by moving only to adjacent pixels. Two pixels are adjacent if they share a corner or an edge. A connected component is maximal if adding a new black pixel to the component will make it disconnected.