Description

Orez likes collecting mysterious data and often arranges them into a matrix for study. Recently, Orez obtained some new data and arranged them into an $n$-row, $m$-column matrix. By observation, Orez found a peculiar number: the count of square submatrices that are symmetric both top-to-bottom and left-to-right. Naturally, Orez wants to know this number, but the matrix is too large to count by hand. Please write a program to compute this number.

Input Format

The first line contains two integers $n$ and $m$. The next $n$ lines each contain $m$ positive integers, representing Orez’s matrix.

Output Format

Output a single integer $ans$, the number of square submatrices that are symmetric both top-to-bottom and left-to-right.

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

27

Hint

• For 30% of the testdata, $1 \le n, m \le 100$.
• For 100% of the testdata, $1 \le n, m \le 1000$, and the values in the matrix do not exceed $10^9$.

Translated by ChatGPT 5