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>

char s[304];
int _a[608][608], (*const a)[608] = _a + 304;
int _b[608][608], (*const b)[608] = _b + 304;

int main() {
	int n, m;
	scanf("%d%d",&n,&m);
	for (int i = 0; i < n; i++) {
		scanf("%s",s);
		for (int j = 0; j < m; j++)
			a[i-j][i+j] = s[j] == '#';
	}
	for (int i = 1-m; i < n; i++) {
		b[i][0] = 0;
		for (int j = 0; j < n+m-1; j++)
			b[i][j+1] = b[i][j] + a[i][j];
	}
	long long ans = 0;
	for (int i = 1-m; i < n; i++)
		for (int j = 1; j < n+m-1; j++) if (a[i][j])
			for (int k = 0; k < j; k++) if (a[i][k]) {
				int d = j-k;
				if (i+d < n) ans += b[i+d][j+1] - b[i+d][k];
				if (i-d > -m) ans += b[i-d][j+1] - b[i-d][k];
			}
	for (int j = 0; j < n+m-1; j++) {
		b[0][j] = 0;
		for (int i = 1-m; i < n; i++)
			b[i+1][j] = b[i][j] + a[i][j];
	}
	for (int i = 0; i < n+m-1; i++)
		for (int j = 2-m; j < n; j++) if (a[j][i])
			for (int k = 1-m; k < j; k++) if (a[k][i]) {
				int d = j-k;
				if (i+d < n+m-1) ans += b[j][i+d] - b[k+1][i+d];
				if (i-d >= 0) ans += b[j][i-d] - b[k+1][i-d];
			}
	printf("%lld\n",ans);
	return 0;
}