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 <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
long long solve(vector<string> S) {
	int H = S.size(), W = S[0].size();
	vector<vector<int> > sum(H + W - 1, vector<int>(H + 1));
	for (int i = 0; i <= H + W - 2; ++i) {
		for (int j = 0; j < H; ++j) {
			sum[i][j + 1] = sum[i][j] + (0 <= i - j && i - j < W && S[j][i - j] == '#' ? 1 : 0);
		}
	}
	long long ans = 0;
	for (int i = 0; i <= H + W - 2; ++i) {
		for (int j = i + 2; j <= H + W - 2; j += 2) {
			int B = (j - i) / 2;
			for (int k = 0; k < H - B; ++k) {
				if (i - k >= W || i - k - B < 0 || S[k][i - k] == '.' || S[k + B][i - k - B] == '.') continue;
				int llim = max(k + B, j - W + 1);
				int rlim = min({ k + 2 * B, H - 1, j }) + 1;
				ans += (sum[j][rlim] - sum[j][llim]) * 2;
				ans -= (0 <= j - (k + B) && j - (k + B) < W && S[k + B][j - (k + B)] == '#' ? 1 : 0);
				ans -= (k + 2 * B < H && 0 <= j - (k + 2 * B) && j - (k + 2 * B) < W && S[k + 2 * B][j - (k + 2 * B)] == '#' ? 1 : 0);
			}
		}
	}
	return ans;
}
vector<string> rotate(vector<string> S) {
	int H = S.size(), W = S[0].size();
	vector<string> ans(W, string(H, '?'));
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			ans[j][H - i - 1] = S[i][j];
		}
	}
	return ans;
}
int main() {
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; ++i) {
		cin >> S[i];
	}
	long long ans = 0;
	for (int i = 0; i < 4; ++i) {
		ans += solve(S);
		S = rotate(S);
	}
	cout << ans / 2 << endl;
	return 0;
}