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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int main()
{
	int h, w;
	cin>>h>>w;
	string s[300];
	for(int i=0; i<h; i++) cin>>s[i];
	char c[1000][1000];
	for(int i=0; i<1000; i++){
		fill(c[i], c[i]+1000, '.');
	}
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(s[i][j]=='#') c[i+300][j+300]='#';
		}
	}

	ll ct1[601][301], ct2[601][301];
	for(int k=0; k<h+w-1; k++){
		ct1[k][0]=0;
		for(int j=1; j<=w; j++){
			ct1[k][j]=ct1[k][j-1];
			if(c[k-j+1+300][j-1+300]=='#') ct1[k][j]++;
		}
	}
	for(int k=0; k<h+w-1; k++){
		ct2[k][0]=0;
		for(int j=1; j<=w; j++){
			ct2[k][j]=ct2[k][j-1];
			if(c[k-w+1+j-1+300][j-1+300]=='#') ct2[k][j]++;
		}
	}

	ll ans=0;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(s[i][j]!='#') continue;
			for(int d=1; i-d>=0 && j+d<w; d++){
				if(s[i-d][j+d]!='#') continue;
				if(i+j-2*d<0) continue;
				ans-=ct1[i+j-2*d][max(0, j-d)];
				ans+=ct1[i+j-2*d][j];
			}
			for(int d=1; i-d>=0 && j+d<w; d++){
				if(s[i-d][j+d]!='#') continue;
				if(i+j+2*d>=h+w-1) continue;
				ans-=ct1[i+j+2*d][min(w, j+d+1)];
				ans+=ct1[i+j+2*d][min(w, j+2*d+1)];
			}
			for(int d=1; i+d<h && j+d<w; d++){
				if(s[i+d][j+d]!='#') continue;
				if(i-j-2*d<=-w) continue;
				ans-=ct2[i-j-2*d+w-1][min(j+d, w)];
				ans+=ct2[i-j-2*d+w-1][min(j+2*d, w)];
			}
			for(int d=1; i+d<h && j+d<w; d++){
				if(s[i+d][j+d]!='#') continue;
				if(i-j+2*d>=h) continue;
				ans-=ct2[i-j+2*d+w-1][max(j-d+1, 0)];
				ans+=ct2[i-j+2*d+w-1][j+1];
			}
		}
	}
	cout<<ans<<endl;
    return 0;
}