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<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=305;
char ss[N][N];
int n,m;
int f[N][N][1205];
int g[N][N][1205];
int calc (int x1,int y1,int x2,int y2,int d)//这个矩形里面的答案 
{
	if (x1>x2) return 0;
	if (y1>y2) return 0;
	return f[x2][y2][d+600]-f[x2][y1-1][d+600]-f[x1-1][y2][d+600]+f[x1-1][y1-1][d+600];
}
int calc1 (int x1,int y1,int x2,int y2,int d)
{
	if (x1>x2) return 0;
	if (y1>y2) return 0;
//	printf("YES\n");
	return g[x2][y2][d+600]-g[x2][y1-1][d+600]-g[x1-1][y2][d+600]+g[x1-1][y1-1][d+600];
}
bool check (int x,int y)	{return x<=n&&y<=m&&x>=1&&y>=1&&ss[x][y]=='#';}
int main()
{
	scanf("%d%d",&n,&m);
	for (int u=1;u<=n;u++)	scanf("%s",ss[u]+1);
	for (int u=1;u<=n;u++)
		for (int i=1;i<=m;i++)
		{
			for (int j=1;j<=1200;j++)
			{
				f[u][i][j]=f[u][i][j]+f[u][i-1][j]+f[u-1][i][j]-f[u-1][i-1][j];
				g[u][i][j]=g[u][i][j]+g[u][i-1][j]+g[u-1][i][j]-g[u-1][i-1][j];
			}
			if (ss[u][i]=='#')	
			{
				f[u][i][u+i+600]++;
				g[u][i][u-i+600]++;
			}
		}
	//	printf("%lld\n",calc1(4,3,4,1,2));
	LL ans=0;
	for (int u=1;u<=n;u++)
		for (int i=1;i<=m;i++)
			{
				for (int d=1;d<=min(n,m);d++)
				{
					if (check(u,i+d)&&check(u+d,i))	ans=ans+calc(1,1,u,i,u+i-d);
				//	if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					if (check(u,i-d)&&check(u+d,i))	
					{
						//if (u==2&&i==3&&d==1) printf("%lld %lld %lld %lld %lld\n",1,i,u,m,calc1(1,i,u,m,u-i-d));
						ans=ans+calc1(1,i,u,m,u-i-d);
						//if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					}
					if (check(u,i+d)&&check(u-d,i)) 
					{
					//	if (u==4&&i==3&&d==1) printf("%lld %lld %lld %lld %lld %lld\n",n,i,u,1,d+u-i,calc1(n,i,u,1,d+u-i));
						ans=ans+calc1(u,1,n,i,d+u-i);
						//if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					}
					if (check(u,i-d)&&check(u-d,i)) ans=ans+calc(u,i,n,m,d+u+i);
				//	if (u==4&&i==3&&d==1) printf("%lld %lld\n",ans,d);
					int cnt=0;
					cnt=cnt+check(u,i+d)+check(u+d,i)+check(u-d,i)+check(u,i-d);
					if (cnt==4) ans=ans-4;
					if (cnt==3) ans--;
				}
				//printf("%lld %lld %lld\n",u,i,ans);
			}
	printf("%lld\n",ans);
	return 0;
}