Problem: There are some coins in the xy-plane. The positions of the coins are represented by a grid of characters with H rows and W columns. If the character at the i-th row and j-th column, s_{ij}, is `#`, there is one coin at point (i,j); if that character is `.`, there is no coin at point (i,j). There are no other coins in the xy-plane.

There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold. There is also no coin at point (x,y) where x or y (or both) is not an integer. Additionally, two or more coins never exist at the same point.

Find the number of triples of different coins that satisfy the following condition:

* Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.



Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|. Two triples are considered the same if the only difference between them is the order of the coins.

Constraints

* 1 \leq H,W \leq 300
* s_{ij} is `#` or `.`.

Input

Input is given from Standard Input in the following format:


H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}


Output

Print the number of triples that satisfy the condition.

Examples

Input

5 4
#.##
.##.
#...
..##
...#


Output

3


Input

5 4
.##
.##.
...
..##
...#


Output

3


Input

13 27
......#.........#.......#..
...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
.#.#.#...###..
...........#...#...#######
..#######..#...#...#.....#
..#.....#..#...#...#.###.#
..#######..#...#...#.#.#.#
..........##...#...#.#####


Output

870

Solution (in CPP):

Solution:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iostream>
#include<string>
#include<sstream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;

#define i64 long long int
int M;

int la;
struct pnt {
	int x, y;
	pnt() {}
	pnt(int _x, int _y) { x = _x; y = _y; }
} a[303 * 303];
int mp[606][606];
void st() {
	memset(mp, -1, sizeof(mp));
	for (int i = 0; i < la; i++)
		mp[a[i].x][a[i].y] = i;
}
bool exis(int x,int y) {
	if (x < 0 || x > M || y < 0 || y > M)return false;
	return mp[x][y] != -1;
}

int sum[606][606];
int Sum(int x, int y1, int y2) {
	if (y2 > M)y2 = M;
	if (y1 <= 0)return sum[x][y2];
	return sum[x][y2] - sum[x][y1 - 1];
}

int main() {
	int row, col; char s[999];
	scanf("%d%d", &row, &col);
//	row = col = 300;
	for (int i = 0; i < row; i++){
		scanf("%s", s);
		for (int j = 0; j < col; j++) {
			if (s[j] == '#') {
				a[la++] = pnt(i + j, i + col - 1 - j);
			}
		}
	}
	M = row - 1 + col - 1;
	i64 res = 0;
	for (int run = 0; run < 2; run++) {
		st();
		for (int k = 1; k <= M; k++) {
			for (int i = 0; i <= M; i++) {
				for (int j = 0; j <= M; j++) {
					sum[i][j] = j == 0 ? 0 : sum[i][j - 1];
					if (exis(i, j) && exis(i, j + k))sum[i][j] ++;
				}
			}
			for (int i = 0; i < la; i++) {
				int X = a[i].x - k;
				if (X >= 0) {
					res += Sum(X, a[i].y - k, a[i].y);
				}
				X = a[i].x + k;
				if (X <= M) {
					res += Sum(X, a[i].y - k, a[i].y);
				}
			}
		}
		for (int i = 0; i < la; i++)swap(a[i].x, a[i].y);
	}
	st();
	for (int i = 0; i < la; i++) {
		for (int k = 1; k <= M; k++) {
			int A = 0, B = 0;
			if (exis(a[i].x + k, a[i].y))A++;
			if (exis(a[i].x - k, a[i].y))A++;
			if (exis(a[i].x, a[i].y + k))B++;
			if (exis(a[i].x, a[i].y - k))B++;
			res -= A * B;
		}
	}
	cout << res << endl;
	return 0;
}