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<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-9;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
char in[310][310];
int s[940][940];
const int S=310;
inline int calc(int a,int b,int c,int d){
	if(a<1||a>=930)return 0;
	if(b<1||b>=930)return 0;
	
	return s[a-1][b-1]+s[c][d]-s[a-1][d]-s[c][b-1];
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%s",in[i]);
	}
	long long ret=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(in[i][j]=='.')continue;
			for(int k=j+1;k<b;k++){
				if(in[i][k]=='.')continue;
				if(k%2!=j%2)continue;
				int di=(k-j)/2;
				if(i-di>=0&&in[i-di][j+di]=='#')ret++;
				if(i+di<a&&in[i+di][j+di]=='#')ret++;
			}
		}
	}
	for(int i=0;i<b;i++){
		for(int j=0;j<a;j++){
			if(in[j][i]=='.')continue;
			for(int k=j+1;k<a;k++){
				if(in[k][i]=='.')continue;
				if(k%2!=j%2)continue;
				int di=(k-j)/2;
				if(i-di>=0&&in[j+di][i-di]=='#')ret++;
				if(i+di<b&&in[j+di][i+di]=='#')ret++;
			}
		}
	}
	//printf("%lld\n",ret);
	ret=-ret;
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(in[i][j]=='#')s[S+i+j][S+i-j]=1;
	}
	for(int i=0;i<S*3;i++){
		for(int j=0;j<S*3-1;j++){
			s[i][j+1]+=s[i][j];
		}
	}
	for(int i=0;i<S*3;i++){
		for(int j=0;j<S*3-1;j++){
			s[j+1][i]+=s[j][i];
		}
	}
	for(int i=0;i<S*3;i++){
		for(int j=0;j<S*3;j++){
			if(calc(i,j,i,j)==0)continue;
			for(int k=j+1;k<S*3;k++){
				if(calc(i,k,i,k)==0)continue;
				int D=k-j;
				ret+=calc(i+D,j,i+D,k);
				ret+=calc(i-D,j,i-D,k);
			}
		}
	}
	for(int i=0;i<S*3;i++){
		for(int j=0;j<S*3;j++){
			if(calc(j,i,j,i)==0)continue;
			for(int k=j+1;k<S*3;k++){
				if(calc(k,i,k,i)==0)continue;
				int D=k-j;
				ret+=calc(j,i+D,k,i+D);
				ret+=calc(j,i-D,k,i-D);
			}
		}
	}
	
	printf("%lld\n",ret);
}

/*
.......
..B....
.......
A...C..
...C...
..C....
.......
.......
*/