Problem: Problem F and F2 are the same problem, but with different constraints and time limits.

We have a board divided into N horizontal rows and N vertical columns of square cells. The cell at the i-th row from the top and the j-th column from the left is called Cell (i,j). Each cell is either empty or occupied by an obstacle. Also, each empty cell has a digit written on it. If A_{i,j}= `1`, `2`, ..., or `9`, Cell (i,j) is empty and the digit A_{i,j} is written on it. If A_{i,j}= `#`, Cell (i,j) is occupied by an obstacle.

Cell Y is reachable from cell X when the following conditions are all met:

* Cells X and Y are different.
* Cells X and Y are both empty.
* One can reach from Cell X to Cell Y by repeatedly moving right or down to an adjacent empty cell.



Consider all pairs of cells (X,Y) such that cell Y is reachable from cell X. Find the sum of the products of the digits written on cell X and cell Y for all of those pairs.

Constraints

* 1 \leq N \leq 500
* A_{i,j} is one of the following characters: `1`, `2`, ... `9` and `#`.

Input

Input is given from Standard Input in the following format:


N
A_{1,1}A_{1,2}...A_{1,N}
A_{2,1}A_{2,2}...A_{2,N}
:
A_{N,1}A_{N,2}...A_{N,N}


Output

Print the sum of the products of the digits written on cell X and cell Y for all pairs (X,Y) such that cell Y is reachable from cell X.

Examples

Input

2
11
11


Output

5


Input

4
1111
11#1
1#11
1111


Output

47


Input

10
76##63##3#
8445669721
75#9542133
3#285##445
749632##89
2458##9515
5952578#77
1#3#44196#
4355#99#1#
298#63587


Output

36065


Input

10
4177143673
7#########
5#1716155#
6#4#####5#
2#3#597#6#
6#9#8#3#5#
5#2#899#9#
1#6#####6#
6#5359657#
5#########


Output

6525

Solution (in CPP):

Solution:
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int INF=2147483647;
int n,m,A[2][1505][1505],U[1505][1505],D[1505][1505];
int f[1505][1505],Left[1505][1505],Right[1505][1505],Min[1505][1505],Max[1505][1505],Top[1505],Bot[1505],Mpoint[1505][1505],Reach[1505];
int Min_Mpoint[1505][1505],Sum_n[1505],Sum_l[1505][1505],Sum_r[1505][1505],Sum_lr[1505][1505];
int q[1505],Only[1505],st,en,sum;
ll ans;
char s[1505][1505];
void calc_LR(int n1,int n2,int m)
{
	for(int i=1;i<=n2;i++)
	for(int j=1;j<=m;j++)
	{
		Left[i][j]=INF,Right[i][j]=-INF;
		if(D[i][j])
		{
			if(i==1)Left[i][j]=Right[i][j]=j;
			if(i>1)
			{
				Left[i][j]=min(Left[i][j],Left[i-1][j]);
				Right[i][j]=max(Right[i][j],Right[i-1][j]);
			}
			if(j>1)
			{
				Left[i][j]=min(Left[i][j],Left[i][j-1]);
				Right[i][j]=max(Right[i][j],Right[i][j-1]);
			}
		}
	}
	Max[n1+1][m+1]=-INF;
	for(int i=m;i>=1;i--)
	{
		if(D[1][i])Min[n1+1][i]=i,Max[n1+1][i]=max(i,Max[n1+1][i+1]);
		else Min[n1+1][i]=INF,Max[n1+1][i]=-INF;
	}
	for(int i=n1;i>=1;i--)
	for(int j=m;j>=1;j--)
	{
		Min[i][j]=INF,Max[i][j]=-INF;
		if(U[i][j])
		{
			Min[i][j]=min(Min[i][j],Min[i+1][j]);
			Max[i][j]=max(Max[i][j],Max[i+1][j]);
			if(j<m)
			{
				Min[i][j]=min(Min[i][j],Min[i][j+1]);
				Max[i][j]=max(Max[i][j],Max[i][j+1]);
			}
		}
	}
}
void calc_TB(int n1,int n2,int m)
{
	for(int i=1;i<=n1;i++)
	for(int j=1;j<=m;j++)
	{
		f[i][j]=INF;
		if(U[i][j])
		{
			f[i][j]=i;
			if(i>1)f[i][j]=min(f[i][j],f[i-1][j]);
			if(j>1)f[i][j]=min(f[i][j],f[i][j-1]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		Top[i]=INF;
		if(D[1][i])
		{
			if(i>1)Top[i]=min(Top[i],Top[i-1]);
			Top[i]=min(Top[i],f[n1][i]);
		}
	}
	for(int i=n2;i>=1;i--)
	for(int j=m;j>=1;j--)
	{
		f[i][j]=-INF;
		if(D[i][j])
		{
			f[i][j]=i;
			if(i<n2)f[i][j]=max(f[i][j],f[i+1][j]);
			if(j<m)f[i][j]=max(f[i][j],f[i][j+1]);
		}
	}
	for(int i=1;i<=m;i++)Bot[i]=f[1][i];
}
void calc_Mp(int n,int m)
{
	for(int i=0;i<=m+1;i++)
	  for(int j=0;j<=m+1;j++)
	    Min_Mpoint[i][j]=INF;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    if(Left[i][j]!=INF)
	      Min_Mpoint[Left[i][j]][Right[i][j]]=min(Min_Mpoint[Left[i][j]][Right[i][j]],i);
	for(int i=1;i<=m;i++)
	  for(int j=m;j>=1;j--)
	    Min_Mpoint[i][j]=min(Min_Mpoint[i][j],min(Min_Mpoint[i-1][j],Min_Mpoint[i][j+1]));
	for(int i=1;i<=m;i++)
	  for(int j=i;j<=m;j++)
	    Mpoint[i][j]=Min_Mpoint[i][j]<=min(Bot[i],Bot[j])?Min_Mpoint[i][j]:INF;
}
void pre_Both(int n,int m)
{
	Sum_n[0]=0;
	for(int i=0;i<=n+1;i++)
	  for(int j=0;j<=m+1;j++)
	    Sum_l[i][j]=Sum_r[i][j]=0;
	for(int i=0;i<=m+1;i++)
	  for(int j=0;j<=m+1;j++)
	    Sum_lr[i][j]=0;
	for(int i=1;i<=n;i++)
	{
		Sum_n[i]=Sum_n[i-1];
		for(int j=1;j<=m;j++)
		{
			if(Left[i][j]<=Right[i][j])
			{
				Sum_n[i]+=D[i][j];
				Sum_l[i][Left[i][j]]+=D[i][j],Sum_r[i][Right[i][j]]+=D[i][j];
				Sum_lr[Left[i][j]][Right[i][j]]+=D[i][j];
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)Sum_r[i][j]+=Sum_r[i-1][j]+Sum_r[i][j-1]-Sum_r[i-1][j-1];
		for(int j=m;j>=1;j--)Sum_l[i][j]+=Sum_l[i-1][j]+Sum_l[i][j+1]-Sum_l[i-1][j+1];
	}
	for(int i=m;i>=1;i--)
	  for(int j=1;j<=m;j++)
	    Sum_lr[i][j]+=Sum_lr[i+1][j]+Sum_lr[i][j-1]-Sum_lr[i+1][j-1];
}
int ask_Both(int i,int j,int l)
{
	l=min(l,min(Bot[i],Bot[j]));
	if(l<Mpoint[i][j])return 0;
	return Sum_n[l]-Sum_l[l][i+1]-Sum_r[l][j-1]+Sum_lr[i+1][j-1];
}
void ins(int y)
{
	Only[y]=Reach[y];
	sum+=Only[y];
	int last=0;
	while(st<=en&&Bot[q[en]]<=Bot[y])
	{
		sum-=Only[q[en]];
		Only[q[en]]-=ask_Both(q[en],y,min(Bot[q[en]],Bot[y]));
		Only[q[en]]+=ask_Both(q[en],y,min(last,Bot[y]));
		sum+=Only[q[en]];
		last=Bot[q[en]];
		en--;
	}
	if(st<=en)
	{
		sum-=Only[q[en]];
		Only[q[en]]-=ask_Both(q[en],y,min(Bot[q[en]],Bot[y]));
		Only[q[en]]+=ask_Both(q[en],y,min(last,Bot[y]));
		sum+=Only[q[en]];
	}
	q[++en]=y;
}
void del(int y)
{
	if(q[st]==y)st++;
	sum-=Only[y];
}
void solve(bool rev,int ln,int rn,int lm,int rm)
{
	if(ln>rn||lm>rm)return;
	if(ln==rn&&lm==rm)return;
	if(rn-ln<rm-lm)
	{
		swap(ln,lm);
		swap(rn,rm);
		rev^=1;
	}
	int mid=(ln+rn)/2;
	solve(rev,ln,mid,lm,rm);
	solve(rev,mid+1,rn,lm,rm);
	int n1=mid-ln+1,n2=rn-mid,m=rm-lm+1;
	for(int i=ln;i<=mid;i++)
	  for(int j=lm;j<=rm;j++)
	    U[i-ln+1][j-lm+1]=A[rev][i][j]=='#'?0:A[rev][i][j]-'0';
	for(int i=mid+1;i<=rn;i++)
	  for(int j=lm;j<=rm;j++)
	    D[i-mid][j-lm+1]=A[rev][i][j]=='#'?0:A[rev][i][j]-'0';
	calc_LR(n1,n2,m);
	calc_TB(n1,n2,m);
	calc_Mp(n2,m);
	pre_Both(n2,m);
	for(int i=1;i<=m;i++)Reach[i]=ask_Both(i,i,Bot[i]);
	for(int i=1;i<=n1;i++)
	{
		st=1,en=0;
		sum=0;
		int nowl=1,nowr=0;
		for(int j=1;j<=m;j++)
		{
			if(Max[i][j]<Min[i][j])continue;
			for(int k=nowr+1;k<=Max[i][j];k++)
				if(i>=Top[k])ins(k);
			for(int k=nowl;k<Min[i][j];k++)
				if(i>=Top[k])del(k);
			nowr=Max[i][j],nowl=Min[i][j];
			ans+=sum*U[i][j];
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    A[0][i][j]=s[i][j],A[1][i][j]=s[j][i];
	solve(0,1,n,1,n);
	printf("%lld\n",ans);
	return 0;
}