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<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int h=333;
const int lim=1000;
char s[1010][1010];
int sum1[1010][1010],sum2[1010][1010];
int main()
{
	int n,m,cnt=0;
	long long la,ans=0;
	scanf("%d%d",&n,&m);
	memset(s,0,sizeof(s));
	for(int i=h+1;i<=h+n;i++)
		scanf("%s",s[i]+h+1);
	memset(sum1,0,sizeof(sum1));
	memset(sum2,0,sizeof(sum2));
	for(int i=1;i<=1000;i++)
		for(int j=1;j<=1000;j++)
		{
			sum1[i][j]=sum1[i-1][j-1]+(s[i][j]=='#');
			sum2[i][j]=sum2[i-1][j+1]+(s[i][j]=='#');
		}
	la=0;
	for(int i=h+1;i<=h+n;i++)
		for(int j=h+1;j<=h+m;j++)
			for(int k=1;k<=300;k++)
			{
				cnt=(s[i-k][j]=='#')+(s[i+k][j]=='#')+(s[i][j-k]=='#')+(s[i][j+k]=='#');
				if(cnt==3)
					ans--;
				else if(cnt==4)
					ans-=4;
				if((s[i-k][j]=='#')&&(s[i][j+k]=='#'))
					ans+=sum1[i+k][j]-sum1[i-1][j-k-1];
				if((s[i+k][j]=='#')&&(s[i][j-k]=='#'))
					ans+=sum1[i][j+k]-sum1[i-k-1][j-1];
				if((s[i+k][j]=='#')&&(s[i][j+k]=='#'))
					ans+=sum2[i][j-k]-sum2[i-k-1][j+1];
				if((s[i-k][j]=='#')&&(s[i][j-k]=='#'))
					ans+=sum2[i+k][j]-sum2[i-1][j+k+1];
			}
	printf("%lld",ans);
	return 0;
}