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 long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSR(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m;
char f[305][305],ff[305][305];
ll ans ;
int pos[605][305][305];
vector<int>cnt[605];
ll sol(){
	rep(i,605) {cnt[i].clear(); rep(j,305)rep(k,305) pos[i][j][k]=0;}
	rep(i,n) rep(j,m){
		if(f[i][j] != '#') continue;
		cnt[i+j].pb(i);
	}
	rep(i,605) SORT(cnt[i]);
	rep(i,605){
		if(cnt[i].empty()) continue;
		rep(j,cnt[i].size()) for(int k=j+1;k<cnt[i].size();k++){
			int dif = cnt[i][k]-cnt[i][j];
			pos[i][dif][cnt[i][j]]++;
		}
	}
	rep(i,605)rep(j,305)rep(k,305){ if(k) pos[i][j][k] += pos[i][j][k-1];}
	ll ret = 0;
	rep(i,n) rep(j,m){
		if(f[i][j] != '#') continue;
		for(int k=i+j+2;k<=n-1+m-1;k+=2){
			int lb = i+1, ub = k-j-(k-i-j)/2-1;
			int x = 0;
			if(0<=lb-1 && lb-1<305) x+=pos[k][(k-i-j)/2][lb-1];//POSL(pos[k][(k-i-j)/2],lb);
			int y = 0;
			if(0<=ub) y+=pos[k][(k-i-j)/2][min(303,ub)];//POSR(pos[k][(k-i-j)/2],ub);
			ans += y-x;
		}
		for(int k=i+j-2;k>=0;k-=2){
			int lb = k-j+1, ub = i-(i+j-k)/2-1;
			int x = 0;
			if(0<=lb-1 && lb-1<305) x+=pos[k][(i+j-k)/2][lb-1];//POSL(pos[k][(i+j-k)/2],lb);
			int y = 0;
			if(0<=ub) y+=pos[k][(i+j-k)/2][min(303,ub)];//POSR(pos[k][(i+j-k)/2],ub);
			ans += y-x;
		}
		
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&m);
	rep(i,n) scanf("%s",&f[i]);
	rep(i,n){
		rep(j,m) for(int k=j+1;k<m;k++){
			if(f[i][j]=='#'&&f[i][k]=='#'&&j%2==k%2){
				int mm = (j+k)/2;
				int d = (k-j)/2;
				if(0<=i-d&&i-d<n&&f[i-d][mm]=='#') ans++;
				if(0<=i+d&&i+d<n&&f[i+d][mm]=='#') ans++;
			}
		}
	}
	rep(i,m){
		rep(j,n) for(int k=j+1;k<n;k++){
			if(f[j][i]=='#'&&f[k][i]=='#'&&j%2==k%2){
				int mm = (j+k)/2;
				int d = (k-j)/2;
				if(0<=i-d&&i-d<m&&f[mm][i-d]=='#') ans++;
				if(0<=i+d&&i+d<m&&f[mm][i+d]=='#') ans++;
			}
		}
	}
	//本質
	ans += sol();
	rep(i,n)rep(j,m) ff[i][j] = f[i][m-1-j];
	rep(i,n)rep(j,m) f[i][j] = ff[i][j];
	ans += sol();
	cout << ans << endl;
}