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<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int H,W;
	char S[301][301];
	int chebi[601][601]={};
	int yokoruiseki[601][601]={};
	int tateruiseki[601][601]={};
	vpint zahyo;
	ll ans=0;
	scan(H);scan(W);
	rep(i,H){
		scan(S[i]);
		rep(j,W){
			if(S[i][j]=='#'){
				zahyo.push_back(mp(W+i-j,i+j));
				chebi[W+i-j][i+j]=1;
				yokoruiseki[W+i-j][i+j+1]=1;
				tateruiseki[W+i-j+1][i+j]=1;
			}
		}
	}
	/*rep(i,H+W){
		rep(j,H+W){
			printf("%c",(chebi[i][j] ? '#' : '.'));
		}
		kaigyo;
	}*/
	rep(i,H+W){
		rep(j,H+W){
			yokoruiseki[i][j+1]+=yokoruiseki[i][j];
		}
	}
	rep(j,H+W){
		rep(i,H+W){
			tateruiseki[i+1][j]+=tateruiseki[i][j];
		}
	}
	/*rep(i,H+W){
		rep(j,H+W+1){
			printf("%d",yokoruiseki[i][j]);
		}
		kaigyo;
	}
	kaigyo;
	rep(i,H+W+1){
		rep(j,H+W){
			printf("%d",tateruiseki[i][j]);
		}
		kaigyo;
	}
	kaigyo;*/
	rep(i,H+W){
		rep(j,H+W){
			if(chebi[i][j]){
				for(int k=j+1;k<H+W;k++){
					if(chebi[i][k]){
						int d=k-j;
						if(i-d>=0) ans+=yokoruiseki[i-d][k+1]-yokoruiseki[i-d][j];
						if(i+d<H+W) ans+=yokoruiseki[i+d][k+1]-yokoruiseki[i+d][j];
					}
				}
				for(int l=i+1;l<H+W;l++){
					if(chebi[l][j]){
						int d=l-i;
						if(j-d>=0) ans+=tateruiseki[l][j-d]-tateruiseki[i+1][j-d];
						if(j+d<H+W) ans+=tateruiseki[l][j+d]-tateruiseki[i+1][j+d];
					}
				}
				//printf("i:%d j:%d ans:%lld\n",i,j,ans);
			}
		}
	}
	prin(ans);
	return 0;
}