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<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;
/*
struct point
{
long long dist; long long name;
bool operator<(const point& rhs) const {
return dist > rhs.dist;
}
};
*/

ll const MAX = 1000;
ll grid[MAX][MAX];
ll h, w;

ll yoko[MAX][MAX];
ll tate[MAX][MAX];

bool ingrid(ll i, ll j) {
	bool flag1 = ((i + j) >= 250);
	bool flag2 = ((i + j) <= 950);
	bool flag3 = (j >= i - 350);
	bool flag4 = (j <= i + 350);
	return flag1 && flag2&&flag3&&flag4;
}

int main() {
	cin >> h >> w;
	REP(i, 0, MAX - 1) {
		REP(j, 0, MAX - 1) {
			grid[i][j] = tate[i][j] = yoko[i][j] = 0;
		}
	}
	REP(i, 1, h) {
		REP(j, 1, w) {
			char c;
			cin >> c;
			if (c == '#') {
				grid[i + j][i - j + 301] = 1;
			}
		}
	}	
	h = 603; w = 603;

	REP(i, 1, h+1) {
		REP(j, 1, w+1) {
			yoko[i][j] = yoko[i][j - 1] + grid[i][j];
		}
	}
	REP(j, 1, w+1) {
		REP(i, 1, h+1) {
			tate[i][j] = tate[i - 1][j] + grid[i][j];
		}
	}
	ll ans = 0;
	REP(i, 1, h) {
		REP(j, 1, w) {
			if (!ingrid(i, j)) continue;
			if (grid[i][j] == 0) continue;
			REP(k, i + 1, h) {
				if (!ingrid(k, j)) break;
				if (grid[k][j] == 0)continue;
				ll r = k - i;
				if (j + r <= w) {
					ll e;
					e = tate[k][j + r] - tate[i - 1][j + r];
					ans += e;

					//cout << e << " "<< i << " "  <<j<< " " << r << endl;
				}
				if (j - r >= 1) {
					ll e;
					e = tate[k][j - r] - tate[i - 1][j - r];
					ans += e;
					//cout << e << " "  << i << " " << j << " " << r << endl;

				}
			}
			REP(l, j + 1, w) {
				if (!ingrid(i, l)) break;
				if (grid[i][l] == 0)continue;
				ll r = l - j;
				if (i + r <= h) {
					ll e;
					e = yoko[i + r][l-1] - yoko[i + r][j];
					ans += e;
					//cout <<e << " " << i << " " << j <<" " << r << endl;

				}
				if (i - r >= 1) {
					ll e;
					e = yoko[i - r][l-1] - yoko[i - r][j];
					ans += e;
					//cout << e << " " << i << " " << j <<  " " << r<< endl;

				}
			}
		}
	}
	cout << ans << endl;
}