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 rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

char s[600][600];
char t[1200][1200];
int sum[1200][1200];
int sum2[1200][1200];

signed main(){
	int h,w;scanf("%d%d",&h,&w);
	int H=2*(h+w),W=2*(h+w);
	map<int,vector<int>>mp;
	map<int,vector<int>>mp2;
	rep(i,H)rep(j,W)t[i][j]='.';
	rep(i,h){
		scanf("%s",s[i]);
		rep(j,w){
			if(s[i][j]=='#'){
				mp[i-j+h+w].push_back(i+j+h+w);
				mp2[i+j+h+w].push_back(i-j+h+w);
				t[i-j+h+w][i+j+h+w]='#';
			}
		}
	}
	rep(i,H)rep(j,W){
		if(j)sum[i][j]+=sum[i][j-1];
		if(t[i][j]=='#')sum[i][j]++;
	}
	rep(i,W)rep(j,H){
		if(j)sum2[j][i]+=sum2[j-1][i];
		if(t[j][i]=='#')sum2[j][i]++;
	}
	//~ rep(i,H)cout<<t[i]<<endl;
	//~ rep(i,H){
		//~ rep(j,W)cout<<sum[i][j];
		//~ cout<<endl;
	//~ }
	//~ cout<<endl;
	//~ rep(i,H){
		//~ rep(j,W)cout<<sum2[i][j];
		//~ cout<<endl;
	//~ }
	int ans=0;
	for(auto&p:mp){
		auto&v=p.second;
		sort(v.begin(),v.end());
		rep(i,v.size())for(int j=i+1;j<v.size();j++){
			int d=v[j]-v[i];
			ans+=sum[p.first-d][v[j]]-sum[p.first-d][v[i]-1];
			ans+=sum[p.first+d][v[j]]-sum[p.first+d][v[i]-1];
		}
	}
	for(auto&p:mp2){
		auto&v=p.second;
		sort(v.begin(),v.end());
		rep(i,v.size())for(int j=i+1;j<v.size();j++){
			int d=v[j]-v[i];
			ans+=sum2[v[j]-1][p.first-d]-sum2[v[i]][p.first-d];
			ans+=sum2[v[j]-1][p.first+d]-sum2[v[i]][p.first+d];
		}
	}
	cout<<ans<<endl;
}
/*
5 11
..#...#....
...........
#...#...#..
...........
..#...#....
*/