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 ALL(c) (c).begin(),(c).end()

const int O = 400;
const int M = 1000;

int f1[1000][1000], f2[1000][1000];

void solve(long long H, long long W, vector<string> s){
	map<int, vector<pair<int, int>>> mpx, mpy;
	for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j) {
		if (s[i][j] == '.') continue;
		int x = i + j + O / 2, y = i - j + O;
		mpx[x].push_back(make_pair(x,y));
		mpy[y].push_back(make_pair(x,y));
		f1[x][y] = f2[x][y] = 1;
	}
	for(int i = 0; i < M; ++i) {
		for(int j = 1; j < M; ++j) {
			f1[i][j] += f1[i][j-1];
		}
	}
	for(int i = 1; i < M; ++i) {
		for(int j = 0; j < M; ++j) {
			f2[i][j] += f2[i-1][j];
		}
	}

	int res = 0;
	for(auto p: mpx) {
		vector<pair<int,int>> v = p.second;
		for(int i = 0; i < v.size(); ++i) for(int j = i + 1; j < v.size(); ++j) {
			auto a = v[i];
			auto b = v[j];
			int y1 = min(a.second, b.second), y2 = max(a.second, b.second);
			int d = y2 - y1; 
			if(a.first - d >= 0) {
				res += f1[a.first - d][y2] - f1[a.first - d][y1 - 1];
				res -= f1[a.first - d][y1] - f1[a.first - d][y1 - 1];
				res -= f1[a.first - d][y2] - f1[a.first - d][y2 - 1];
			}

			if(a.first + d < M) {
				res += f1[a.first + d][y2] - f1[a.first + d][y1 - 1];
				res -= f1[a.first+d][y1] - f1[a.first + d][y1 - 1];
				res -= f1[a.first+d][y2] - f1[a.first + d][y2 - 1];
			}
		}
	}
	for(auto p: mpy) {
		vector<pair<int,int>> v = p.second;
		for(int i = 0; i < v.size(); ++i) for(int j = i + 1; j < v.size(); ++j) {
			auto a = v[i];
			auto b = v[j];
			int d = abs(a.first - b.first);
			int x1 = min(a.first, b.first), x2 = max(a.first, b.first);
			if(a.second - d >= 0) {
				res += max(f2[x2][a.second - d] - f2[x1 - 1][a.second - d], 0);
			}
			if(a.second + d < M) {
				res += max(f2[x2][a.second + d] - f2[x1 - 1][a.second + d], 0);
			}
		}
	}
	cout << res << endl;
}

int main(){	
	long long W;
	long long H;
	scanf("%lld",&H);
	vector<string> s(H-1+1);
	scanf("%lld",&W);
	for(int i = 0 ; i <= H-1 ; i++){
		cin >> s[i];
	}
	solve(H, W, s);
	return 0;
}