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 <cstdlib>
#include <algorithm>
#include <map>
#include <utility>
#define LL long long
using namespace std;
const int Maxn = 310;
int mp[Maxn][Maxn], tot;
int n, m;
char s[Maxn][Maxn];
int f[2][Maxn<<1][Maxn], g[2][Maxn<<1][Maxn];
int ffind(int x, int y) {
	if(x < 0 || x >= n || y < 0 || y >= m) return 0;
	return mp[x][y] > 0 ? 1 : 0;
}
int calcf(int op, int x, int y) {
	if(y < 0 || x < 0 || x > n-1+m-1) return 0;
	if(y >= n) return f[op][x][n-1];
	return f[op][x][y];
}
int calcg(int op, int x, int y) {
	if(y < 0 || x < 0 || x > n-1+m-1) return 0;
	if(y >= n) return g[op][x][n-1];
	return g[op][x][y];
}
int main() {
	int i, j, k;
	scanf("%d%d", &n, &m);
	for(i = 0; i < n; i++) scanf("%s", s[i]);
	for(i = 0; i < n; i++){
		for(j = 0; j < m; j++){
			if(s[i][j] == '#') mp[i][j] = ++tot;
		}
	}
	for(i = 0; i < n; i++){
		for(j = 0; j < m; j++){
			if(mp[i][j] == 0) continue;
			f[0][i+m-1-j][i] = 1;
			f[1][i+j][i] = 1;
		}
	}
	for(i = 0; i <= n-1+m-1; i++){
		for(j = 1; j < n; j++){
			f[0][i][j] += f[0][i][j-1];
			f[1][i][j] += f[1][i][j-1];
		}
	}
	LL ans = 0;
	for(k = 2; k <= n+m; k += 2){
		memset(g, 0, sizeof(g));
		for(i = 0; i < n; i++){
			for(j = 0; j < m; j++){
				if(mp[i][j] == 0) continue;
				g[0][i+m-1-j][i] = ffind(i-k/2, j-k/2);
				g[1][i+j][i] = ffind(i-k/2, j+k/2);
			}
		}
		for(i = 0; i <= n-1+m-1; i++){
			for(j = 1; j < n; j++){
				g[0][i][j] += g[0][i][j-1];
				g[1][i][j] += g[1][i][j-1];
			}
		}
		for(i = 0; i < n; i++){
			for(j = 0; j < m; j++){
				if(mp[i][j] == 0) continue;
				int x = i, y = j;
				if(ffind(x+k/2, y+k/2) > 0){
					ans += calcf(0, i+m-1-j+k, i+k-1) - calcf(0, i+m-1-j+k, i+k/2-1);
					ans += calcf(0, i+m-1-j-k, i-1) - calcf(0, i+m-1-j-k, i-k/2-1);
				}
				if(ffind(x-k/2, y-k/2) > 0){
					ans += calcf(0, i+m-1-j+k, i+k/2) - calcf(0, i+m-1-j+k, i);
					ans += calcf(0, i+m-1-j-k, i-k/2) - calcf(0, i+m-1-j-k, i-k);
				}
				if(ffind(x+k/2, y-k/2) > 0){
					ans += calcf(1, i+j+k, i+k-1) - calcf(1, i+j+k, i+k/2);
					ans += calcf(1, i+j-k, i-1) - calcf(1, i+j-k, i-k/2);
				}
				if(ffind(x-k/2, y+k/2) > 0){
					ans += calcf(1, i+j+k, i+k/2-1) - calcf(1, i+j+k, i);
					ans += calcf(1, i+j-k, i-k/2-1) - calcf(1, i+j-k, i-k);
				}
				ans += calcg(0, i+m-1-j+k, i+k) - calcg(0, i+m-1-j+k, i+k/2-1);
				ans += calcg(0, i+m-1-j-k, i) - calcg(0, i+m-1-j-k, i-k/2-1);
				ans += calcg(1, i+j+k, i+k) - calcg(1, i+j+k, i+k/2-1);
				ans += calcg(1, i+j-k, i) - calcg(1, i+j-k, i-k/2-1);
			}
		}
	}
	printf("%lld\n", ans/3);
	return 0;
}