Counting Tetris Figures

Ivica is developing his first computer game: a clone of Tetris. In his game, there are five different Tetris figures that can be rotated (by 90° any number of times) and colored before being placed on a matrix. A figure cannot be placed if any of its cells would lie outside the matrix or if it overlaps an already placed figure. Ivica’s sister, Marica, played the game and placed these figures in the matrix. Moreover, the placement obeys the rule that adjacent figures (two figures that share a common side or touch at a corner) have different colors.

Your task is to analyze the final Tetris matrix and count how many figures of each type there are.

The five figures are tetrominoes (each made up of 4 cells) defined in their canonical forms as follows:

• Square: \(\{(0,0), (0,1), (1,0), (1,1)\}\)
• I shape: \(\{(0,0), (1,0), (2,0), (3,0)\}\)
• T shape: \(\{(0,0), (0,1), (0,2), (1,1)\}\)
• L shape: \(\{(0,0), (1,0), (2,0), (2,1)\}\)
• Z shape: \(\{(0,0), (0,1), (1,1), (1,2)\}\)

Note that a figure may be rotated (by 90° increments) arbitrarily. To determine the type of a figure, you should find its 8-connected component (cells are connected if they touch horizontally, vertically, or diagonally) and then normalize its cell coordinates (by subtracting the minimum row and column). Then, by comparing with the above templates (up to rotations), you can determine the figure type.

Output the counts of the figures in the following order: Square, I shape, T shape, L shape, Z shape, separated by spaces.

inputFormat

The input begins with a line containing two integers n and m (the number of rows and columns of the matrix). The following n lines each contain m characters. Each character is either '.' (indicating an empty cell) or a letter indicating the color of the figure occupying that cell. It is guaranteed that each figure occupies exactly 4 cells and that the figures (which may be rotated) do not overlap and do not touch each other (even at a corner) if they are of different colors.

outputFormat

Output five integers separated by spaces, where the numbers represent the counts of the Square, I shape, T shape, L shape, and Z shape pieces respectively.

sample

7 8
AA.B....
AA.B....
...B.D..
...B.D..
CCC..DD.
.C..EE..
.....EE.

1 1 1 1 1