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;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000002
long long ans = 0;
int get(vector<string> S){
	int H = S.size();
	int W = S[0].size();
	int ans = 0;
	for(int y0=0;y0<H;y0++){
		for(int x0=0;x0<W;x0++){
			for(int y1=0;y1<H;y1++){
				for(int x1=0;x1<W;x1++){
					for(int y2=0;y2<H;y2++){
						for(int x2=0;x2<W;x2++){
							if(x0==x1&&y0==y1)continue;
							if(abs(y0-y1)+abs(x0-x1)!=abs(y1-y2)+abs(x1-x2))continue;
							if(abs(y0-y1)+abs(x0-x1)!=abs(y0-y2)+abs(x0-x2))continue;
							if(S[y0][x0]!='#'||S[y1][x1]!='#'||S[y2][x2]!='#')continue;
							ans++;
							if(y0==4&&x0==23)cout<<x0<<','<<y0<<','<<x1<<','<<y1<<','<<x2<<','<<y2<<endl;
						}
					}
				}
			}
		}
	}
	return ans/6;
}

void calc(vector<string> S){
	int H = S.size();
	int W = S[0].size();
	
	vector<vector<int>> cnt(H,vector<int>(W,0));
	
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(S[i][j]=='#'){
				cnt[i][j]=1;
			}
			if(i!=0){
				if(j+1!=W)cnt[i][j]+=cnt[i-1][j+1];
			}
		}
	}
	
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			
			int y = i,x = j;
			while(true){
				y++,x++;

				if(y<0||y>=H||x<0||x>=W)break;
				if(S[i][x]=='#'&&S[y][j]=='#'){
					int d = abs(y-i);
					int a = i-1,b = j-d+1;
					if(b<0){
						a -= abs(b);
						b=0;
					}
					if(a>=0){
						ans += cnt[a][b];
						
					}
					
					a = i-d,b = j;
					if(a>=0){
						ans -= cnt[a][b];
					}

					
				}
			}
			
			
		}
	}
}

int main(){
	
	int H,W;
	cin>>H>>W;
	
	vector<string> S(H);
	for(int i=0;i<H;i++)cin>>S[i];
	

	
	//cout<<get(S)<<endl;
	
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			for(int t=i-1,b=i+1;t>=0&&b<H;t--,b++){
				if(S[t][j]=='#'&&S[b][j]=='#'){
					int k = b-i;
					if(j-k>=0)if(S[i][j-k]=='#')ans++;
					if(j+k<W)if(S[i][j+k]=='#')ans++;
				}
			}

			for(int l=j-1,r=j+1;l>=0&&r<W;l--,r++){
				if(S[i][l]=='#'&&S[i][r]=='#'){
					int k = r-j;
					if(i-k>=0)if(S[i-k][j]=='#')ans++;
					if(i+k<H)if(S[i+k][j]=='#')ans++;
				}
			}
			

			

		}
	}
	
	calc(S);
	reverse(S.begin(),S.end());
	calc(S);
	for(int i=0;i<H;i++)reverse(S[i].begin(),S[i].end());
	calc(S);
	reverse(S.begin(),S.end());
	calc(S);
	cout<<ans<<endl;
	
	return 0;
}