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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
//#define ivorysi
#define MAXN 100005
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
	res = 0;char c = getchar();T f = 1;
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) out(x / 10);
	putchar('0' + x % 10);
}
int H,W;
char s[305][305];
int sum[605][605];
vector<int> row[605],col[605];
int Query1(int x1,int x2,int y) {
	if(x2 < x1) return 0;
	if(y < 1 || y > H + W) return 0;
	x2 = min(x2,H + W);
	x1 = max(x1,1);
	return sum[x2][y] - sum[x1 - 1][y] - sum[x2][y - 1] + sum[x1 - 1][y - 1];
}
int Query2(int x,int y1,int y2) {
	if(y2 < y1) return 0;
	if(x < 1 || x > H + W) return 0;
	y2 = min(y2,H + W);
	y1 = max(y1,1);
	return sum[x][y2] - sum[x][y1 - 1] - sum[x - 1][y2] + sum[x - 1][y1 - 1];
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	read(H);read(W);
	for(int i = 1 ; i <= H ; ++i) {
		scanf("%s",s[i] + 1);
	}
	for(int i = 1 ; i <= H ; ++i) {
		for(int j = 1 ; j <= W ; ++j) {
			if(s[i][j] == '#') {
				sum[i + j][i - j + W]++;
				row[i + j].pb(i - j + W);
				col[i - j + W].pb(i + j);
			}
		}
	}
	for(int i = 1 ; i <= H + W ; ++i) {
		for(int j = 1 ; j <= H + W ; ++j) {
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}
	int64 ans = 0;
	for(int i = 1 ; i <= H + W ; ++i) {
		int s = row[i].size();
		sort(row[i].begin(),row[i].end());
		for(int j = 0 ; j < s ; ++j) {
			for(int k = j + 1 ; k < s ; ++k) {
				int l = row[i][k] - row[i][j];
				ans += Query2(i - l,row[i][j],row[i][k]);
				ans += Query2(i + l,row[i][j],row[i][k]);
			}
		}
	}
	for(int i = 1 ; i <= H + W ; ++i) {
		int s = col[i].size();
		sort(col[i].begin(),col[i].end());
		for(int j = 0 ; j < s ; ++j) {
			for(int k = j + 1 ; k < s ; ++k) {
				int l = col[i][k] - col[i][j];
				ans += Query1(col[i][j] + 1,col[i][k] - 1,i - l);
				ans += Query1(col[i][j] + 1,col[i][k] - 1,i + l);
			}
		}
	}
	out(ans);enter;
	return 0;
}