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 signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int H,W;
string S[303];

int R[2003][2003];
int L[2003][2003];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,2000) FOR(x,2000) {
		if(y&&x) R[y][x]=R[y-1][x-1];
		if(y) L[y][x]=L[y-1][x+1];
		if(y-700>=0 && y-700<H && x-700>=0 && x-700<W) {
			R[y][x]+=S[y-700][x-700]=='#';
			L[y][x]+=S[y-700][x-700]=='#';
		}
		
	}
	
	ll ret=0;
	FOR(y,H) FOR(x,W) {
		for(l=1;l<=300;l++) {
			int num[11]={};
			if(y-l>=0) num[8]=S[y-l][x]=='#';
			if(y+l<H) num[2]=S[y+l][x]=='#';
			if(x-l>=0) num[4]=S[y][x-l]=='#';
			if(x+l<W) num[6]=S[y][x+l]=='#';
			num[7]=L[y+700][x-l+700]-L[y-l+700][x+700]-num[4];
			num[3]=L[y+l+700][x+700]-L[y+700][x+l+700]-num[2];
			num[9]=R[y+700][x+l+700]-R[y-l+700][x+700]-num[6];
			num[1]=R[y+l+700][x+700]-R[y+700][x-l+700]-num[2];
			ll p=ret;
			ret+=num[2]*(num[6]*num[8]+num[4]*num[8]+num[4]*num[6]);
			ret+=num[4]*num[6]*num[8];
			ret+=num[1]*num[6]*num[8];
			ret+=num[3]*num[4]*num[8];
			ret+=num[9]*num[2]*num[4];
			ret+=num[7]*num[2]*num[6];
		}
	}
	
	cout<<ret<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}