cho.sh

Finding a Perfect Square

From a grid of digits, pick cells whose row and column indices each form an arithmetic sequence, concatenate the digits, and find the largest perfect square possible.

Medium5Brute forceMathNumber theoryImplementationNo attempts yetTime limit2sMemory limit128 MB

Problem

You are given a table A with N rows and M columns. Each cell contains a single digit.

Yeondu wants to choose one or more distinct cells. When the chosen cells are listed in the order they are picked, their row numbers must form an arithmetic sequence, and their column numbers must also form an arithmetic sequence. Concatenating the digits written in the chosen cells, in the order they were picked, forms a single integer.

Find the largest perfect square among the integers Yeondu can form. A perfect square is a number obtained by squaring some integer.

Input

The first line contains two integers N and M separated by a space.

Each of the next N lines contains one row of the table, from row 1 to row N in order. On each line, the digits of that row are given from column 1 to column M with no spaces between them.

Output

Print the largest perfect square Yeondu can form on the first line. If no perfect square can be formed, print -1.

Constraints

  • 1 ≤ N, M ≤ 9
  • Each digit written in the table is between 0 and 9, inclusive.