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>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_W=300,MAX_H=300,INF=1e8;
int H,W;
typedef pair<int,int> P;
P coi[MAX_H*MAX_W],coi2[MAX_H*MAX_W],rotcoi[MAX_H*MAX_W];
char temp[MAX_H+8][MAX_W+8+1];
int psm[MAX_H+8][MAX_W+8+1];
int main(){
	cin>>H>>W;
	int N=0;
	ll ans=0;
	REP(i,H){
		string s;
		cin>>s;
		REP(j,W){
			if (s[j]=='#'){
				coi[N++]=P(i,j);
			}
		}
	}
	REP(par,2){
		int N2=0;
		REP(i,N){
			if ((coi[i].first+coi[i].second)%2==0){
				coi2[N2]=P((coi[i].first+coi[i].second)/2,(-coi[i].first+coi[i].second)/2);
				N2++;
			}
		}
		REP(rot,4){
			REP(i,MAX_H+8){
				REP(j,MAX_W+8){
					temp[i][j]='.';
				}
			}
			REP(i,N2){
				rotcoi[i]=coi2[i];
			}
			{
				int mih=INF,miw=INF;
				REP(i,N2){
					mih=min(rotcoi[i].first,mih);
					miw=min(rotcoi[i].second,miw);
				}
				REP(i,N2){
					rotcoi[i].first-=mih;
					rotcoi[i].second-=miw;
				}
			}
			REP(i,N2){
				temp[rotcoi[i].first][rotcoi[i].second]='#';
			}
			memset(psm,0,sizeof(psm));
			REP(h,MAX_H+8){
				REP(w,MAX_W+8){
					psm[h][w+1]=psm[h][w];
					if (temp[h][w]=='#'){
						psm[h][w+1]=psm[h][w]+1;
					}
				}
			}
			FOR(wid,2,MAX_W+8+1){
				REP(h,MAX_H+8-wid+1){
					REP(w,MAX_W+8-wid+1){
						if (temp[h][w]=='#' && temp[h][w+wid-1]=='#'){
							ans+=psm[h+wid-1][w+wid-1]-psm[h+wid-1][w];
						}
					}
				}
			}
			REP(i,N2){
				swap(coi2[i].first,coi2[i].second);
				coi2[i].second*=-1;
			}
		}
		REP(i,N){
			coi[i].first++;
		}
	}
	cout<<ans<<endl;
				
		
	return 0;
}