A map of the island is drawn on checkered paper (the cells of the island are shaded). At the same time, the island is a checker-convex figure, that is, each horizontal or vertical line on the map either does not intersect the island, or intersects it along a segment (the intersection line does not contain breaks). Also, the island is a connected figure, that is, any two cells of the island are connected by a path, every two neighboring cells of which have a common side.
A cell is considered adjacent to an island if it does not belong to the island, but shares a side or corner with one of the island's cells. For example, on the following map, the cells of the island are shaded, and the cells adjacent to the island are marked with asterisks.
The plane must fly around the island in the adjacent cells without invading the territory of the island. The program should create a flight route for the aircraft. The plane starts flying around the island in one of the neighboring cells with the island and must visit all the cells adjacent to the island exactly once. In this case, the aircraft can move from one cell to another cell only if these cells have a common side.
Imprint
The program receives as input two numbers N and M, written in separate lines, — number of rows and columns of the island map (3 ≤ N ≤ 100, 3 ≤ M ≤ 100). Next is a map of the island — N lines, each containing M characters. Each map symbol can be either the character ".", which means a cell that does not belong to the island, or the character "#", which means a cell of the island. In this case, the island does not touch the edge of the map.
Let's introduce a coordinate system on the map. The first coordinate is the line number, the lines are numbered from top to bottom with numbers from 1 to N. The second coordinate — column number, columns are numbered from left to right with numbers from 1 to M.
Input
The program should display the coordinates of the map cells in the order they were flown by the aircraft. Each output line must contain two numbers x and y — aircraft coordinates separated by a space (1 ≤ x ≤ N, 1 ≤ y ≤ M). The plane must visit each cell adjacent to the island exactly once. Every two consecutive cells in the output must have a common side. Any possible route around the island can be displayed.
Examples
| # |
Input |
Output |
| 1 |
6
7
.......
.......
.......
.###...
.###...
.......
|
3 1
3 2
3 3
34
3 5
4 5
5 5
6 5
6 4
6 3
6 2
6 1
5 1
4 1 |