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>
#define gc getchar()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
inline int inn()
{
	int x,ch;while((ch=gc)<'0'||ch>'9');
	x=ch^'0';while((ch=gc)>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^'0');return x;
}
#define Ss(x,y) (x>=1&&x<=n&&y>=1&&y<=m&&v[x][y])
const int N=1010;int v[N][N],s[N][N];char str[N][N];
inline int S(int a,int b,int c,int d)
{
	return s[c][d]-s[a-1][d]-s[c][b-1]+s[a-1][b-1];
}
int main()
{
	int n=inn(),m=inn(),ans=0;
	rep(i,1,n) scanf("%s",str[i]+1);
	rep(i,1,n) rep(j,1,m)
		v[i+j][i-j+m]=(str[i][j]=='#');
	int nn=n+m,mm=n-1+m;n=nn,m=mm;
	rep(i,1,n) rep(j,1,m) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+v[i][j];
	rep(i,1,n) rep(j,1,m) rep(k,j+2,m)
	{
		int d=k-j;if(!v[i][j]||!v[i][k]) continue;
		if(i-d>=1) ans+=S(i-d,j+1,i-d,k-1);
		if(i+d<=n) ans+=S(i+d,j+1,i+d,k-1);
	}
	rep(i,1,m) rep(j,1,n) rep(k,j+2,n)
	{
		int d=k-j;if(!v[j][i]||!v[k][i]) continue;
		if(i-d>=1) ans+=S(j+1,i-d,k-1,i-d);
		if(i+d<=m) ans+=S(j+1,i+d,k-1,i+d);
	}
	rep(i,1,n) rep(j,1,m)
	{
		if(!v[i][j]) continue;
		rep(d,1,max(n,m))
		{
			if(Ss(i-d,j)&&Ss(i,j-d)) ans++;
			if(Ss(i-d,j)&&Ss(i,j+d)) ans++;
			if(Ss(i+d,j)&&Ss(i,j-d)) ans++;
			if(Ss(i+d,j)&&Ss(i,j+d)) ans++;
		}
	}
	return !printf("%d\n",ans);
}