ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Equal Squares

Time limit: 2.0 second
Memory limit: 128 MB
During a discussion of problems at the Petrozavodsk Training Camp, Vova and Sasha argued about who of them could in 300 minutes find a pair of equal squares of the maximal size in a matrix of size N × M containing lowercase English letters. Squares could overlap each other but could not coincide. He who had found a pair of greater size won. Petr walked by, looked at the matrix, said that the optimal pair of squares had sides K, and walked on. Vova and Sasha still cannot find this pair. Can you help them?

Input

The first line contains integers N and M separated with a space. 1 ≤ NM ≤ 500. In the next N lines there is a matrix consisting of lowercase English letters, M symbols per line.

Output

In the first line, output the integer K which Petr said. In the next two lines, give coordinates of upper left corners of maximal equal squares. If there exist more than one pair of equal squares of size K, than you may output any of them. The upper left cell of the matrix has coordinates (1, 1), and the lower right cell has coordinates (NM). If there are no equal squares in the matrix, then output 0.

Sample

inputoutput
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
3
1 1
3 3
Problem Author: Vladimir Yakovlev
Problem Source: The XIth USU Programing Championship, October 7, 2006
To submit the solution for this problem go to the Problem set: 1486. Equal Squares