Anthill

Time limit0.5sMemory limit256 MB

Summary

In a grid of free cells and walls, find every 2x2-seeded connected room and report each room's size and how many rooms touch it directly.

Level: Medium6 of 10
Topics: Graph, BFS, Union-find
Solved: No attempts yet

Problem

The floor plan of one underground level of an anthill can be pictured as a grid of $R$ rows and $S$ columns. Each cell of the grid is either free or a wall. Two free cells are connected if you can get from one to the other by a sequence of steps, where each step moves to an adjacent free cell up, down, left, or right.

A room is a group of connected free cells that is at least 2 cells wide everywhere. More precisely, a room is a set of free cells that satisfies these conditions:

It contains 4 free cells that form a square 2 columns wide and 2 rows tall.
If a $2 \times 2$ piece is placed on those 4 cells, the room consists of exactly the free cells that the piece can reach by moving up, down, left, or right over free cells only.

The same cell can belong to more than one room. For example, the following anthill has two rooms of size 4 each, and the center cell belongs to both of them:

#..
...
..#

Two rooms are directly connected if you can get from some cell of one room to some cell of the other by moving up, down, left, and right over free cells without passing through a cell of a third room. Of course, two rooms that share a cell are also directly connected. No cell belongs to more than two rooms.

Write a program that finds all rooms and, for each room, determines its size (the number of cells it contains) and the number of rooms it is directly connected to.

Input

The first line contains two positive integers $R$ and $S$ ( $2 \le R, S \le 100$ ), the number of rows and the number of columns of the anthill.

Each of the next $R$ lines contains a string of $S$ characters describing one row of the anthill. Free cells are marked with . (a period) and walls with #.

The anthill always contains at least one room.

Output

Print as many lines as there are rooms in the anthill. For each room, print one line with two positive integers separated by a space: the size of the room and the number of rooms it is directly connected to.

Print the rooms from the largest to the smallest. Among rooms of the same size, print first the one with more directly connected rooms.

Examples2

Example 1
Input
```
3 3
#..
...
..#
```
Expected output
```
4 1
4 1
```

Example 2

Input

7 8
#..#....
....##..
##.#....
##.....#
#.#..#..
........
.##.....

Expected output