Diamonds joker#1767
All your answers will be questioned
"Interstande 60"
Arsen has a deck of cards. Not just one, but as many as . Only the diamond joker is missing. (You do not know why you need a diamond joker?) However, he has a rectangular sheet of paper from a notebook, from which he can cut out this joker.
Each cell of the sheet is colored in one of colors, and the joker must be a diamond consisting of cells of the same color (it does not have to be red; a black or, for example, a blue diamond joker would not surprise anyone).
In this problem, a diamond with center at cell (r_0, c_0) ( — row number, — column number) and radius is defined as the set of cells (r_i, c_i) satisfying |r_i - r_0| + |c_i - c_0| \leq R.
Of course, a larger joker is more useful in the game, so Arsen wants to cut the largest possible diamond made of cells of the same color from the sheet. Write a program that will help him do this.
The first line of the input file contains two integers and (1 \leq m, n \leq 500), the dimensions of the rectangle (in cells). Each of the next lines contains uppercase Latin letters, each representing a particular color. The second line of the input file corresponds to the first row, the (m+1)-th row corresponds to the -th row of the rectangle.
Output three integers r_0, c_0, and , separated by spaces—the row and column number of the center and the radius of the largest diamond. If there are several diamonds, output the one with the smallest row number. If there is still ambiguity, output the one with the smallest column number.
The output numbers must also satisfy the inequalities:
that is, the diamond for the joker must lie entirely within the rectangle.
Beispiel 1