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<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
int s[310][310],n,m;
char sa[310][310],sb[310][310];
int get(int x,int y){
	if(x<=0){
		y+=1-x;
		x=1;
	}
	return y<=m?s[x][y]:0;
}
ll count(){
	int i,j,k,d;
	ll res;
	memset(s,0,sizeof(s));
	for(i=n;i>0;i--){
		for(j=m;j>0;j--){
			s[i][j]=s[i+1][j+1]+(sa[i][j]=='#');
		}
	}
	res=0;
	for(i=1;i<=n;i++){
		for(j=0;i+j<=n&&1+j<=m;j++){
			if(sa[i+j][1+j]=='.')continue;
			for(k=j+1;i+k<=n&&1+k<=m;k++){
				if(sa[i+k][1+k]=='.')continue;
				d=k-j;
				res+=get(i+j-d,1+j+d)-get(i+j,1+j+d*2);	
			}
		}
	}
	for(i=2;i<=m;i++){
		for(j=0;1+j<=n&&i+j<=m;j++){
			if(sa[1+j][i+j]=='.')continue;
			for(k=j+1;1+k<=n&&i+k<=m;k++){
				if(sa[1+k][i+k]=='.')continue;
				d=k-j;
				res+=get(1+j-d,i+j+d)-get(1+j,i+j+d*2);
			}
		}
	}
	return res;
}
void rot(){
	int i,j;
	memset(sb,0,sizeof(sb));
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)sb[j][n-i+1]=sa[i][j];
	}
	swap(n,m);
	memcpy(sa,sb,sizeof(sb));
}
int main(){
	int i;
	ll res;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%s",sa[i]+1);
	res=count();
	rot();
	res+=count();
	rot();
	res+=count();
	rot();
	res+=count();
	printf("%lld",res);
}