Finding a Perfect Square

Time limit2sMemory limit128 MB

Summary

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.

Level: Medium5 of 10
Topics: Brute force, Math, Number theory, Implementation
Solved: No attempts yet

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.

Examples6

Example 1
Input
```
2 3
123
456
```
Expected output
```
64
```
Example 2
Input
```
5 5
00000
00000
00200
00000
00000
```
Expected output
```
0
```

Example 3

Input

Expected output

Example 4

Input

Expected output

Example 5

Input

Expected output

-1

Example 6

Input

Expected output