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>
#define llint long long

using namespace std;

int h, w, n;
char c[305][305];
llint sum[705][705];
llint Zero = 355;

llint calc()
{
	llint ret = 0;
	for(int u = -n; u <= n; u++){
		for(int v = 0; v <= 2*n; v++){
			sum[Zero+u][v] = 0;
		}
	}
	for(int x = 1; x <= n; x++){
		for(int y = 1; y <= n; y++){
			if(c[x][y] == '.') continue;
			int u = x-y, v = x+y;
			sum[Zero+u][v]++;
		}
	}
	for(int u = -n; u <= n; u++){
		for(int v = 0; v <= 2*n; v++){
			if(v > 0) sum[Zero+u][v] += sum[Zero+u][v-1];
		}
	}
	for(int x = 1; x <= n; x++){
		for(int y = 1; y <= n; y++){
			if(c[x][y] == '.') continue;
			for(int d = 1; d <= n; d++){
				if(x+d>n || y+d>n) break;
				if(c[x+d][y+d] == '.') continue;
				int u = x-y, v = x+y;
				if(Zero+u-2*d >= 0 && v+2*d < 705) ret += sum[Zero+u-2*d][v+2*d] - sum[Zero+u-2*d][v];
			}
		}
	}
	return ret;
}

char t[305][305];
void rot()
{
	for(int x = 1; x <= n; x++){
		for(int y = 1; y <= n; y++){
			t[x][y] = c[y][n-x+1];
		}
	}
	for(int x = 1; x <= n; x++){
		for(int y = 1; y <= n; y++){
			c[x][y] = t[x][y];
		}
	}
}

int main(void)
{
	cin >> h >> w;
	n = max(h, w);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			c[i][j] = '.';
		}
	}
	for(int i = 1; i <= h; i++){
		for(int j = 1; j <= w; j++){
			cin >> c[j][i];
		}
	}
	
	
	llint ans = 0;
	for(int i = 0; i < 4; i++){
		ans += calc();
		rot();
	}
	cout << ans << endl;
	
	return 0;
}