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 pb push_back
#define int long long
#define mp make_pair
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
int field[314][314];
int rsum[650][650], lsum[650][650];
vector< pair<int,int> > rup[650],lup[650];
signed main(){
	int h,w;
	cin>>h>>w;
	for(int i=0;i<h;i++){
		string s;
		cin>>s;
		for(int j=0;j<w;j++){
			if( s[j] == '#' ) field[i+1][j+1] = 1;
		}
	}
	for(int i=0;i<=h+1;i++){
		for(int j=0;j<=w+1;j++){
			if( field[i][j] == 1 ){
				rup[i+j].pb( mp(i,j) );
				lup[j-i+h+1].pb( mp(i,j) );
				rsum[i+j][i] = rsum[i+j][i-1]+1;
				lsum[j-i+h+1][i] = lsum[j-i+h+1][i-1]+1;
			}
			else{
				rsum[i+j][i] = rsum[i+j][i-1];
				lsum[j-i+h+1][i] = lsum[j-i+h+1][i-1];
			}
		}
	}
	for(int i=2;i<=600;i++){
		for(int j=1;j<=h+w;j++){
			if( rsum[i][j-1] > 0 && rsum[i][j] == 0 ) rsum[i][j] = rsum[i][j-1];
			if( lsum[i][j-1] > 0 && lsum[i][j] == 0 ) lsum[i][j] = lsum[i][j-1];
		}
	}
	int ans = 0;
	for(int i=2;i<=600;i++){
		for(int j=0;j<rup[i].size();j++){
			for(int k=j+1;k<rup[i].size();k++){
				pair<int,int> p1 = rup[i][j], p2 = rup[i][k];
				int ax = p1.first, ay = p1.second, bx = p2.first, by = p2.second;
				int mdis = abs(ax-bx)+abs(ay-by);
				if( i - mdis >= 2 ){
					ans += max(0LL ,rsum[ i-mdis ][ max( bx - mdis/2 - 1 , 0LL) ] - rsum[ i-mdis ][ max(ax - mdis/2 ,0LL)]);
					//if(rsum[ i-mdis ][ bx - mdis/2 ] - rsum[ i-mdis ][ ax - mdis/2 - 1])cout<<ax<<" "<<ay<<" "<<bx<<" "<<by<<endl;
				}
				if( i + mdis <= h+w ){
					ans += max(0LL, rsum[ i+mdis][min( bx + mdis/2 - 1, h+w) ] - rsum[ i+mdis ][min( ax + mdis/2, h+w)]);
					//if(rsum[ i + mdis][ bx + mdis/2] - rsum[ i+mdis ][ ax + mdis/2 - 1])cout<<ax<<" "<<ay<<" "<<bx<<" "<<by<<endl;
				}
			}
		}
	}
	int ans2 = 0;
	for(int i=2;i<=600;i++){
		for(int j=0;j<lup[i].size();j++){
			for(int k=j+1;k<lup[i].size();k++){
				pair<int,int> p1 = lup[i][j], p2 = lup[i][k];
				int ax = p1.first, ay = p1.second, bx = p2.first, by = p2.second;
				int mdis = abs(ax-bx)+abs(ay-by);
				//cout<<i<<" "<<mdis<<endl;
				if( i - mdis >= 2 ){
					ans2 += lsum[ i-mdis ][min( bx + mdis/2 , h+w)] - lsum[ i-mdis ][ min(ax + mdis/2 - 1 ,h+w)];
					//cout<<i-mdis<<" "<<bx + mdis/2<<" "<<ax + mdis/2<<endl;
				}
				if( i + mdis <= h+w ){
					ans2 += lsum[ i + mdis][ max( bx - mdis/2 , 0LL) ] - lsum[ i+mdis ][max( ax - mdis/2 - 1 , 0LL)];
					//cout<<i+mdis<<" "<<bx - mdis/2<<" "<<ax - mdis/2<<endl;
				}
			}
		}
	}
	cout<< ans + ans2 <<endl;
	return 0;
}