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>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=300+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
}
int n,m;
char s[N][N];
void input()
{
	n=read<int>(),m=read<int>();
	For(i,1,n)scanf("%s",s[i]+1);
}
ll ans;
int w[N<<1][N<<1],h[N<<1][N<<1],a[N<<1][N<<1];
struct node
{
	int x,y;
}e[N*N];
int top;
void work()
{	
	int x,y;
	int Max=max(n,m);
	For(i,1,n)For(j,1,m)if(s[i][j]=='#')
	{
		x=i+j,y=i-j+Max;
		e[++top]=(node){x,y};
		a[x][y]=1;
	}
	Max<<=1;
	For(i,1,Max)For(j,1,Max)w[i][j]=w[i][j-1]+a[i][j],h[i][j]=h[i-1][j]+a[i][j];
	For(i,1,top)
	{
		x=e[i].x,y=e[i].y;
		for(int d=2;d<=Max;d+=2)
		{
			if(y+d<=Max&&a[x][y+d])
			{
				if(x-d>0)ans+=w[x-d][y+d]-w[x-d][y-1];
				if(x+d<=Max)ans+=w[x+d][y+d]-w[x+d][y-1];
			}
			if(x+d<=Max&&a[x+d][y])
			{
				if(y-d>0)ans+=h[x+d-1][y-d]-h[x][y-d];
				if(y+d<=Max)ans+=h[x+d-1][y+d]-h[x][y+d];
			}
		}
	}
	write(ans,'\n');
}
int main()
{
	//file();
	input();
	work();
	return 0;
}