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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); }

const int MAXN = 1500;

bool canreachd[MAXN][MAXN]; int minreachd[MAXN][MAXN], maxreachd[MAXN][MAXN]; // u[x][y] or d[hu+x][y] for x==0 -> leftmost/rightmost cell of d[0] that this square can reach
int top[MAXN][MAXN]; // u[x][y] or d[hu+x][y] for x==0 -> topmost row that can reach this square
int bot[MAXN][MAXN]; // d[x][y] -> bottommost row that this square can reach

bool isreachable[MAXN][MAXN]; int minreachedby[MAXN][MAXN], maxreachedby[MAXN][MAXN]; // d[x][y] -> leftmost/rightmost cell of d[0] that can reach this square

int firstjoin[MAXN][MAXN]; // row of topmost cell that is reachable from d[0][y1] and d[0][y2]
ll sumtotal[MAXN]; // sum of squares on d[x] reachable from d[0]
ll sumbefore[MAXN][MAXN]; // sum of squares on d[x] reachable from d[0], but not from d[0][y'] for y'>=y
ll sumafter[MAXN][MAXN]; // sum of squares on d[x] reachable from d[0], but not from d[0][y'] for y'<=y
ll sumbetween[MAXN][MAXN]; // sum of squares reachable from d[0], but not from d[0][y'] for y'<=y1 or y'>=y2

ll calc(int y1, int y2, int xlim) {
	ll ret;
	if (xlim < firstjoin[y1][y2]) {
		ret = 0;
	} else {
		// total number of squares (x<=xlim) that can be reached from somewhere
		// - squares (x<=xlim) that can only be reached from y < y2
		// - squares (x<=xlim) that can only be reached from y > y1
		// + squares (x<=xlim) that can only be reached from y1 < y < y2 -> when can only happen when x < firstjoin[y1][y2]
		ret = sumtotal[xlim] - sumbefore[xlim][y2] - sumafter[xlim][y1] + sumbetween[y1][y2];
		//printf("\t\t(%lld-%lld-%lld+%lld)\n", sumtotal[xlim], sumbefore[xlim][y2], sumafter[xlim][y1], sumbetween[y1][y2]);
	}
	//printf("\tcalc(%d,%d,%d)=%lld [%d<%d]\n", y1, y2, xlim, ret, xlim, firstjoin[y1][y2]);
	return ret;
}

ll cnt[MAXN], sum;
int q[MAXN], qtail, qhead;

void add(int y) {
	cnt[y] = calc(y, y, bot[0][y]); sum += cnt[y];
	int xlim = -1;
	while (qtail < qhead && bot[0][q[qhead - 1]] <= bot[0][y]) {
		int yy = q[--qhead];
		ll delta = calc(yy, y, bot[0][yy]) - calc(yy, y, xlim);
		cnt[yy] -= delta; sum -= delta; xlim = bot[0][yy];
	}
	if (qtail < qhead) {
		int yy = q[qhead - 1];
		ll delta = calc(yy, y, bot[0][y]) - calc(yy, y, xlim);
		cnt[yy] -= delta; sum -= delta;
	}
	q[qhead++] = y;
}
void rem(int y) {
	sum -= cnt[y]; cnt[y] = 0;
	if (qtail < qhead) { assert(q[qtail] >= y); if (q[qtail] == y) ++qtail; }
}

int reachable[MAXN], nreachable;

ll bf(const vector<string> &u, const vector<string> &d, int x, int y) {
	int hu = SZ(u), hd = SZ(d), w = SZ(u[0]); assert(SZ(d[0]) == w);
	vector<vector<bool>> can(hu + hd, vector<bool>(w, false));
	queue<pair<int, int>> q; ll ret = 0;
	can[x][y] = true; q.push(MP(x, y));
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		if (x >= hu) ret += d[x - hu][y] - '0';
		if (x + 1 < hu + hd && !(x + 1 < hu&&u[x + 1][y] == '#') && !(x + 1 >= hu&&d[x + 1 - hu][y] == '#') && !can[x + 1][y]) {
			can[x + 1][y] = true; q.push(MP(x + 1, y));
		}
		if (y + 1 < w && !(x < hu&&u[x][y + 1] == '#') && !(x >= hu&&d[x - hu][y + 1] == '#') && !can[x][y + 1]) {
			can[x][y + 1] = true; q.push(MP(x, y + 1));
		}
	}
	return ret;
}
ll bf(const vector<string> &g, int x, int y) {
	int h = SZ(g), w = SZ(g[0]);
	vector<vector<bool>> can(h, vector<bool>(w, false));
	queue<pair<int, int>> q; ll ret = -(g[x][y] - '0');
	can[x][y] = true; q.push(MP(x, y));
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		ret += g[x][y] - '0';
		if (x + 1 < h && g[x + 1][y] != '#' && !can[x + 1][y]) {
			can[x + 1][y] = true; q.push(MP(x + 1, y));
		}
		if (y + 1 < w && g[x][y + 1] != '#' && !can[x][y + 1]) {
			can[x][y + 1] = true; q.push(MP(x, y + 1));
		}
	}
	return ret;
}

// keep track of set of top cells of d that are reachable from u[x][y] and of sum of different cells in d that are reachable from them
ll solve(const vector<string> &u, const vector<string> &d) {
	int hu = SZ(u), hd = SZ(d), w = SZ(u[0]); assert(SZ(d[0]) == w);
	//printf("solving:\n"); REP(x, hu) printf("%s\n", u[x].c_str()); REP(y, w) printf("-"); puts(""); REP(x, hd) printf("%s\n", d[x].c_str());

	for (int x = hu; x >= 0; --x) for (int y = w - 1; y >= 0; --y) {
		canreachd[x][y] = false, minreachd[x][y] = w, maxreachd[x][y] = -1; if (x < hu && u[x][y] == '#' || x == hu && d[0][y] == '#') continue;
		if (x == hu) { canreachd[x][y] = true; minreachd[x][y] = maxreachd[x][y] = y; }
		if (x + 1 <= hu && canreachd[x + 1][y]) { canreachd[x][y] = true; minreachd[x][y] = min(minreachd[x][y], minreachd[x + 1][y]); maxreachd[x][y] = max(maxreachd[x][y], maxreachd[x + 1][y]); }
		if (y + 1 <  w  && canreachd[x][y + 1]) { canreachd[x][y] = true; minreachd[x][y] = min(minreachd[x][y], minreachd[x][y + 1]); maxreachd[x][y] = max(maxreachd[x][y], maxreachd[x][y + 1]); }
	}
	REPE(x, hu) REP(y, w) {
		top[x][y] = hu; if (x < hu && u[x][y] == '#' || x == hu && d[0][y] == '#') continue;
		if (x < hu) top[x][y] = x;
		if (x - 1 >= 0) top[x][y] = min(top[x][y], top[x - 1][y]);
		if (y - 1 >= 0) top[x][y] = min(top[x][y], top[x][y - 1]);
	}
	for (int x = hd - 1; x >= 0; --x) for (int y = w - 1; y >= 0; --y) {
		bot[x][y] = -1; if (d[x][y] == '#') continue;
		bot[x][y] = x;
		if (x + 1 < hd) bot[x][y] = max(bot[x][y], bot[x + 1][y]);
		if (y + 1 < w ) bot[x][y] = max(bot[x][y], bot[x][y + 1]);
	}
	REP(x, hd) REP(y, w) {
		isreachable[x][y] = false, minreachedby[x][y] = w, maxreachedby[x][y] = -1; if (d[x][y] == '#') continue;
		if (x == 0) { isreachable[x][y] = true; minreachedby[x][y] = maxreachedby[x][y] = y; }
		if (x - 1 >= 0 && isreachable[x - 1][y]) { isreachable[x][y] = true; minreachedby[x][y] = min(minreachedby[x][y], minreachedby[x - 1][y]); maxreachedby[x][y] = max(maxreachedby[x][y], maxreachedby[x - 1][y]); }
		if (y - 1 >= 0 && isreachable[x][y - 1]) { isreachable[x][y] = true; minreachedby[x][y] = min(minreachedby[x][y], minreachedby[x][y - 1]); maxreachedby[x][y] = max(maxreachedby[x][y], maxreachedby[x][y - 1]); }
	}
	//REP(x, hd) REP(y, w) printf("(%d,%d): %d %d %d\n", x, y, isreachable[x][y] ? 1 : 0, minreachedby[x][y], maxreachedby[x][y]);
	REP(x, hd) sumtotal[x] = 0;
	REP(x, hd) REP(y, w) if (isreachable[x][y]) sumtotal[x] += d[x][y] - '0';
	FOR(x, 1, hd) sumtotal[x] += sumtotal[x - 1];
	REP(x, hd) REP(y, w) sumbefore[x][y] = 0;
	REP(x, hd) REP(y, w) if (isreachable[x][y] && maxreachedby[x][y] + 1 < w) sumbefore[x][maxreachedby[x][y] + 1] += d[x][y] - '0';
	REP(x, hd) FOR(y, 1, w) sumbefore[x][y] += sumbefore[x][y - 1];
	FOR(x, 1, hd) REP(y, w) sumbefore[x][y] += sumbefore[x - 1][y];
	REP(x, hd) REP(y, w) sumafter[x][y] = 0;
	REP(x, hd) REP(y, w) if (isreachable[x][y] && minreachedby[x][y] - 1 >= 0) sumafter[x][minreachedby[x][y] - 1] += d[x][y] - '0';
	REP(x, hd) for (int y = w - 2; y >= 0; --y) sumafter[x][y] += sumafter[x][y + 1];
	FOR(x, 1, hd) REP(y, w) sumafter[x][y] += sumafter[x - 1][y];
	REP(y1, w) REP(y2, w) sumbetween[y1][y2] = 0;
	REP(x, hd) REP(y, w) if (isreachable[x][y] && minreachedby[x][y] - 1 >= 0 && maxreachedby[x][y] + 1 < w) sumbetween[minreachedby[x][y] - 1][maxreachedby[x][y] + 1] += d[x][y] - '0';
	FOR(dy, 1, w) REP(y1, w-dy) { int y2 = y1 + dy; sumbetween[y1][y2] += sumbetween[y1 + 1][y2] + sumbetween[y1][y2 - 1] - sumbetween[y1 + 1][y2 - 1]; }
	REP(y1, w) REP(y2, w) firstjoin[y1][y2] = hd;
	REP(x, hd) REP(y, w) if (isreachable[x][y]) firstjoin[minreachedby[x][y]][maxreachedby[x][y]] = min(firstjoin[minreachedby[x][y]][maxreachedby[x][y]], x);
	for (int dy = w - 1; dy >= 1; --dy) REP(y1, w - dy) { int y2 = y1 + dy; firstjoin[y1 + 1][y2] = min(firstjoin[y1 + 1][y2], firstjoin[y1][y2]); firstjoin[y1][y2 - 1] = min(firstjoin[y1][y2 - 1], firstjoin[y1][y2]); }
	REP(y1, w) REP(y2, w) if (bot[0][y1] < firstjoin[y1][y2] || bot[0][y2] < firstjoin[y1][y2]) firstjoin[y1][y2] = hd;

	ll ret = 0;
	REP(x, hu) {
		int l = 0, r = 0; qhead = qtail = 0; sum = 0; REP(y, w) cnt[y] = 0;
		nreachable = 0; REP(y, w) if (top[hu][y] <= x) reachable[nreachable++] = y;
		//printf("reachable%d:", x); REP(i, nreachable) printf(" %d", reachable[i]); puts("");
		REP(y, w) {
			if (!canreachd[x][y]) continue;
			while (r < nreachable && maxreachd[x][y] >= reachable[r]) add(reachable[r++]);
			while (l < r && minreachd[x][y] > reachable[l]) rem(reachable[l++]);
			//printf("\t%d: %d..%d [%d..%d)\n", y, minreachd[x][y], maxreachd[x][y], l, r);
			assert(l < r && reachable[l] == minreachd[x][y] && reachable[r - 1] == maxreachd[x][y]);
			ret += (u[x][y] - '0')*sum;
			//ll chk = bf(u, d, x, y); if (chk != sum) { printf("err(%d,%d): have=%lld want=%lld\n", x, y, sum, chk); exit(0); }
		}
	}
	return ret;
}

vector<string> rot(const vector<string> &g) {
	int h = SZ(g), w = SZ(g[0]); vector<string> ret(w, string(h, '?')); REP(x, h) REP(y, w) ret[y][x] = g[x][y]; return ret;
}

ll solve(const vector<string> &g) {
	int h = SZ(g), w = SZ(g[0]);
	if (h < w) return solve(rot(g));
	if (h == 1) return 0;
	int hu = h / 2, hd = h - hu;
	vector<string> u(hu, string(w, '?')); REP(x, hu) REP(y, w) u[x][y] = g[x][y];
	vector<string> d(hd, string(w, '?')); REP(x, hd) REP(y, w) d[x][y] = g[hu + x][y];
	return solve(u, d) + solve(u) + solve(d);
}


int n;
char g[MAXN][MAXN + 1];

ll solve() {
	vector<string> g(n, string(n, '?')); REP(x, n) REP(y, n) g[x][y] = ::g[x][y];
	return solve(g);
}


void run() {
	scanf("%d", &n); REP(x, n) scanf("%s", g[x]);
	printf("%lld\n", solve());
}

void verify() {
	ll have = solve();
	ll want = 0; REP(x, n) REP(y, n) if (g[x][y] != '#') { vector<string> gg(n, string(n, '?')); REP(i, n) REP(j, n) gg[i][j] = g[i][j]; want += (ll)(g[x][y] - '0')*bf(gg, x, y); }
	if (have == want) { printf("."); return; }
	printf("err: have=%lld want=%lld\n", have, want);
	REP(x, n) printf("%s\n", g[x]);
	exit(0);
}

void stress1() {
	REP(rep, 100000) {
		int freq = 2 + rand() % 5;
		n = 1 + rand() % 40; REP(x, n) { REP(y, n) g[x][y] = rand() % freq == 0 ? '#' : '1' + rand() % 9; g[x][n] = '\0'; }
		verify();
	}
}

void stress2() {
	REP(rep, 10) {
		n = MAXN; REP(x, n) { REP(y, n) g[x][y] = rand() % 4 == 0 ? '#' : '1' + rand() % 9; g[x][n] = '\0'; }
		solve();
		printf(".");
	}
}


void stress3() {
	REP(rep, 1) {
		n = MAXN; REP(x, n) { REP(y, n) g[x][y] = '9'; g[x][n] = '\0'; }
		printf("%lld\n", solve());
		ll want = 0; REP(x, n) REP(y, n) { ll cur = (ll)(n - x)*(n - y) - 1; want += (ll)cur * 9 * 9; }
		printf("want=%lld\n", want);
	}
}

void test() {
	scanf("%d", &n); REP(x, n) scanf("%s", g[x]);
	verify();
}


int main() {
	run();
	//stress1();
	//stress2();
	//stress3();
	//test();
	return 0;
}