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>
const int N=305;
long long ans;
int H,W,a[N][N],b[N*2][N*2],c[N*2][N*2],i,j,d;
char cc[N];
int main(){
	scanf("%d%d",&H,&W);
	for(i=1;i<=H;++i)for(scanf("%s",cc+1),j=1;j<=W;++j)if(cc[j]=='#')
		a[i][j]=b[i-j+W][i+j-1]=c[i+j-1][i-j+W]=1;
	for(i=1;i<N*2;++i)for(j=1;j<N*2;++j)b[i][j]+=b[i][j-1],c[i][j]+=c[i][j-1];
	for(d=1;d<=std::min(H,W);d++){
		for(i=1;i<=H-d;++i)for(j=1;j<=W-d;++j)if(a[i][j]==1 && a[i+d][j+d]==1){
			int x=i-j+W,y=i+j-1;
			if(x>d*2)ans+=b[x-d*2][y+d*2]-b[x-d*2][y-1];
			if(x+d*2<N*2)ans+=b[x+d*2][y+d*2]-b[x+d*2][y-1];
		}
		for(i=1;i<=H-d;++i)for(j=d+1;j<=W;++j)if(a[i][j]==1 && a[i+d][j-d]==1){
			int x=i-j+W,y=i+j-1;
			if(y>d*2)ans+=c[y-d*2][x+d*2]-c[y-d*2][x-1];
			if(y+d*2<N*2)ans+=c[y+d*2][x+d*2]-c[y+d*2][x-1];
		}
		for(i=1;i<=H;++i)for(j=1;j<=W;++j)if(a[i][j]){
			int p=i>d && j>d?a[i-d][j-d]:0,q=i>d && j+d<=W?a[i-d][j+d]:0,
				r=i+d<=H && j+d<=W?a[i+d][j+d]:0,s=i+d<=H && j>d?a[i+d][j-d]:0;
			ans-=p*q+q*r+r*s+s*p;
		}
	}
	printf("%lld\n",ans);
	return 0;
}