400451: GYM100186 C The road

— I think it is imprudent to show such documentation to a complete stranger. — Chris returned the pile to Alice and was determined to end the conversation and be off.

— He is not a stranger! — a bit grumpy voice came from the Chris's back. He turned around. Yes, it was Simon. Their paths crossed several times before. Simon considered himself to be a great programmer and an even greater leader. The fact that all his projects and firms burst like soap bubbles didn't bother him at all. He was gifted with ability to present the bright future of his next idea in such a way that those who had already seen the inglorious ending of his previous plans, began to believe that this time Simon could actually succeed.

— As a matter of fact, we huddle in this building temporarily. We are planning a new office in the "Blue tractor-driver" settlement. The forest will be just outside the window! Though, there'll be a problem with the road for special machinery because of the fences. But I have all the necessary documents, so owners will have to move! — It was obvious that Simon was eager to show his importance.

A lot of wealthy people settled down in the "Blue tractor-driver" lately, thus the cost of the land increased considerably. It is clear to Chris that the area where Simon wants to build the house is almost surrounded by the forest and it is hard to lay the service lines and build the road to the building. Furthermore, the owners don't like the fact that a part of their property can become a road.

The map of the settlement is represented by a N × M rectangle. Let's assume that it is divided into unit squares. Private properties are also represented by rectangles with sides parallel to the map boundaries. Every unit square is either belongs completely to a private property or doesn't belong to any private property at all. Any two properties do not overlap. Squares with coordinates (1, 1) (upper left corner) and (N, M) (lower right corner) do not belong to any private property. The road has to connect these two corners.

Every segment of the road, which Simon wants to build, has to be parallel to one of the map sides. The road has to be of the unit width (equal to the width of a side of a unit square) and every square has to either belong to the road completely or do not belong to the road at all. Lastly, the road has to be the shortest possible.

It is obvious that some parts of the properties will be expropriated. Let K denote the cost — the highest possible amount of squares of the property that can be expropriated. You task is to determine the minimal cost of the construction of the shortest possible road and to print out the road.

The first line contains integers N and M separated by a space (2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000) — dimensions of the settlement map.

The following N lines contain M symbols each which describe the map. Empty squares are denoted by ".", private property squares are denoted by lower-case Latin letters from "a" to "z". Each owner has only one connected rectangular area. Different letters only differentiate touching regions from each other.

Output in the first line the integer K — the minimal cost of the construction of the shortest possible road.

In the following N + M - 1 lines output the coordinates of the squares which describe the road in the order from (1, 1) (upper left corner) to (N, M) (lower right corner).

4 5
.aa..
.aacc
bb.cc
bb...

1
1 1
2 1
2 2
3 2
3 3
3 4
4 4
4 5

4 5
.aa..
.aa..
bbcc.
bbcc.

2
1 1
1 2
1 3
1 4
1 5
2 5
3 5
4 5