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 <cstring>
#include <algorithm>
#include <cmath>

typedef long long LL;
const int MaxN = 600;
using namespace std;

int n, m = 300, w;
int a[MaxN + 5][MaxN + 5]; 
int c[MaxN + 5][MaxN + 5], r[MaxN + 5][MaxN + 5];
char s[305][305];
struct NODE {
	int x, y;
}p[300 * 300 + 5];

int main() 
{
	while(~scanf("%d%d", &n, &w)) {
		for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); 
		int tot = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= w; j++) {
				if(s[i][j] == '#') {
					int x = i + j - 1, y = i - j + m;
					p[++tot] = (NODE){x, y};
					a[x][y] = 1;
				}
			}
		}
		m *= 2;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				c[i][j] = c[i - 1][j] + a[i][j]; 
				r[i][j] = r[i][j - 1] + a[i][j];
			}
		}
		long long res = 0;
		for (int i = 1; i <= tot; i++) {
			int x = p[i].x, y = p[i].y;
			for (int d = 2; d <= m; d += 2) {
				if(x + d <= m && a[x + d][y]) {
					if(y + d <= m) res += c[x + d - 1][y + d] - c[x][y + d];
					if(y - d >= 0) res += c[x + d - 1][y - d] - c[x][y - d];
				}
				if(y + d <= m && a[x][y + d]) {
					if(x + d <= m) res += r[x + d][y + d] - r[x + d][y - 1]; 
					if(x - d >= 0) res += r[x - d][y + d] - r[x - d][y - 1];
				}
			}
		}
		printf("%lld\n", res);
	}
	return 0;
}