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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int grid[2000][2000];
int n, m, ans;
void dodiag1(int x, int y, int d)
{
//	if (x != 801 || y != 801 || d != 1) return;
	int x2 = x+d;
	int y2 = y+d;

	int a1 = x-d;
	int b1 = y+d;

	int a2 = a1+d;
	int b2 = b1+d;

	int i1 = x+d;
	int j1 = y-d;
	int i2 = i1+d;
	int j2 = j1+d;

//	printf("%lld %lld %lld %lld\n", x2, y2, a2, b2);
	int am = 0;
	int a = a1;
	int b = b1;
	while (a <= a2 && b <= b2)
	{
		am += grid[a][b];
		a++;
		b++;
	}
	a = i1;
	b = j1;
	while (a <= i2 && b <= j2)
	{
		am += grid[a][b];
		a++;
		b++;
	}
	while (x2 <= 800+n && y2 <= 800+m)
	{
		if (grid[x][y] && grid[x2][y2]) ans += am;
		am -= grid[a1++][b1++];
		am += grid[++a2][++b2];
		am -= grid[i1++][j1++];
		am += grid[++i2][++j2];
		x++;
		y++;
		x2++;
		y2++;
	}
}
void dodiag2(int x, int y, int d)
{
//	if (x != 801 || y != 801 || d != 1) return;
	int x2 = x+d;
	int y2 = y-d;

	int a1 = x+d;
	int b1 = y+d;

	int a2 = a1+d;
	int b2 = b1-d;

	int i1 = x-d;
	int j1 = y-d;
	int i2 = i1+d;
	int j2 = j1-d;

//	printf("%lld %lld %lld %lld\n", x2, y2, a2, b2);
	int am = 0;
	int a = a1;
	int b = b1;
	while (a < a2 && b > b2)
	{
		am += grid[a][b];
		a++;
		b--;
	}
	a = i1;
	b = j1;
	while (a < i2 && b > j2)
	{
		am += grid[a][b];
		a++;
		b--;
	}
	while (x2 <= 800+n && y2 >= 800)
	{
		am -= grid[a1++][b1--];
		am -= grid[i1++][j1--];
		if (grid[x][y] && grid[x2][y2]) 
		{
		//	if (am) printf("%lld %lld, %lld %lld\n", x, y, x2, y2);
			ans += am;
		}
		am += grid[a2++][b2--];
		am += grid[i2++][j2--];
		x++;
		y--;
		x2++;
		y2--;
	}
}
#undef int
int main()
{
	#define int ll
	scanf("%lld%lld", &n, &m);
	for (int i = 800+1; i <= 800+n; i++)
	{
		for (int j = 800+1; j <= 800+m; j++) 
		{
			char a;
			scanf(" %c", &a);
			if (a == '#') grid[i][j] = 1;
		}
	}
	for (int i = 800+1; i <= 800+n; i++) 
	{
		for (int d = 1; d <= max(n, m); d++) dodiag1(i, 801, d);
	}
	for (int i = 800+2; i <= 800+m; i++) 
	{
		for (int d = 1; d <= max(n, m); d++) dodiag1(801, i, d);
	}
	for (int i = 800+1; i <= 800+n; i++) 
	{
		for (int d = 1; d <= max(n, m); d++) dodiag2(i, 800+m, d);
	}
	for (int i = 800+1; i < 800+m; i++) 
	{
		for (int d = 1; d <= max(n, m); d++) dodiag2(801, i, d);
	}
	printf("%lld\n", ans);
}