Orez很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近，Orez又得到了一些数据，并已经把它们排成了一个n行m列的矩阵。通过观察，Orez发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。 Orez自然很想知道这个数是多少，可是矩阵太大，无法去数。只能请你编个程序来计算出这个数。

文件的第一行为两个整数n和m。接下来n行每行包含m个正整数，表示Orez得到的矩阵。

文件中仅包含一个整数answer，表示矩阵中有answer个上下左右对称的正方形子矩阵。

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
数据范围
对于30%的数据 n，m≤100
对于100%的数据 n，m≤1000 ，矩阵中的数的大小≤109

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int maxn=1010;

typedef unsigned long long ull;

typedef long long ll;

int v[maxn][maxn];

int n,m;

ll ans;

ull h1[maxn][maxn],h2[maxn][maxn],h3[maxn][maxn],h4[maxn][maxn],b1[maxn],b2[maxn];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),m=rd();

	int i,j,l,r,mid;

	ull g1,g2,g3,g4;

	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	v[i][j]=rd();

	for(b1[0]=b2[0]=1,i=1;i<=n;i++)	b1[i]=b1[i-1]*233,b2[i]=b2[i-1]*2333;

	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)	h1[i][j]=h1[i-1][j]*233+h1[i][j-1]*2333-h1[i-1][j-1]*233*2333+v[i][j];

	for(i=1;i<=n;i++)	for(j=m;j>=1;j--)	h2[i][j]=h2[i-1][j]*233+h2[i][j+1]*2333-h2[i-1][j+1]*233*2333+v[i][j];

	for(i=n;i>=1;i--)	for(j=1;j<=m;j++)	h3[i][j]=h3[i+1][j]*233+h3[i][j-1]*2333-h3[i+1][j-1]*233*2333+v[i][j];

	for(i=n;i>=1;i--)	for(j=m;j>=1;j--)	h4[i][j]=h4[i+1][j]*233+h4[i][j+1]*2333-h4[i+1][j+1]*233*2333+v[i][j];

	for(i=1;i<=n;i++)	for(j=1;j<=m;j++)

	{

		l=1,r=min(min(i,j),min(n-i+1,m-j+1))+1;

		while(l<r)

		{

			mid=l+r>>1;

			g1=h1[i][j]-h1[i-mid][j]*b1[mid]-h1[i][j-mid]*b2[mid]+h1[i-mid][j-mid]*b1[mid]*b2[mid];

			g2=h2[i][j]-h2[i-mid][j]*b1[mid]-h2[i][j+mid]*b2[mid]+h2[i-mid][j+mid]*b1[mid]*b2[mid];

			g3=h3[i][j]-h3[i+mid][j]*b1[mid]-h3[i][j-mid]*b2[mid]+h3[i+mid][j-mid]*b1[mid]*b2[mid];

			g4=h4[i][j]-h4[i+mid][j]*b1[mid]-h4[i][j+mid]*b2[mid]+h4[i+mid][j+mid]*b1[mid]*b2[mid];

			if(g1==g2&&g1==g3&&g1==g4)	l=mid+1;

			else	r=mid;

		}

		ans+=l-1;

		l=1,r=min(min(i,j),min(n-i,m-j))+1;

		while(l<r)

		{

			mid=l+r>>1;

					g1=h1[i][j]-h1[i-mid][j]*b1[mid]-h1[i][j-mid]*b2[mid]+h1[i-mid][j-mid]*b1[mid]*b2[mid];

				j++,g2=h2[i][j]-h2[i-mid][j]*b1[mid]-h2[i][j+mid]*b2[mid]+h2[i-mid][j+mid]*b1[mid]*b2[mid];

			i++,j--,g3=h3[i][j]-h3[i+mid][j]*b1[mid]-h3[i][j-mid]*b2[mid]+h3[i+mid][j-mid]*b1[mid]*b2[mid];

				j++,g4=h4[i][j]-h4[i+mid][j]*b1[mid]-h4[i][j+mid]*b2[mid]+h4[i+mid][j+mid]*b1[mid]*b2[mid];

			i--,j--;

			if(g1==g2&&g1==g3&&g1==g4)	l=mid+1;

			else	r=mid;

		}

		ans+=l-1;

	}

	printf("%lld",ans);

	return 0;

}