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;
typedef long long Long;
typedef vector<int> VI;
typedef vector<VI> VVI;


int main() {
	int H, W;
	cin >> H >> W;
	vector<string> V(H+W, string(H+W, '.'));
	int id = 0;
	for (int i = 0; i < H; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); ++j) {
			if (s[j] == '#') {
				V[i+j][i+W-1-j] = '#';//id++ + '0';
			}
		}
	}
//	for(string v : V) {
//		cout << v << endl;
//	}
	int N = H + W;
	VVI A(N, VI(N, 0));
	for (int i = 0; i < N; ++i) {
		int s = 0;
		for (int j = 0; j < N; ++j) {
			s += V[i][j] == '#';
			A[i][j] = s;
			if (i) A[i][j] += A[i-1][j];
		}
	}
	auto sum = [&](int i0, int i1, int j0, int j1) {
		if (i0 > i1) return 0;
		if (j0 > j1) return 0;
//		cout << i0 << " " << j0 << " " << i1 << " " << j1 << " " << N << endl;
		int s = A[i1][j1];
		if (j0 > 0) s -= A[i1][j0-1];
		if (i0 > 0) s -= A[i0-1][j1];
		if (j0 > 0 && i0 > 0) s += A[i0-1][j0-1];
		return s;
	};
	long long t = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (V[i][j] == '#') {
				for (int k = 1; (k+i) < N && (k+j) < N; ++k) {
					// left and down
					if (V[i][j+k] == '#') {
						t += sum(i+k, i+k, j, j+k);
					}
					if (V[i+k][j] == '#') {
						t += sum(i+1, i+k, j+k, j+k);
					}
				}
				for (int k = 1; (i-k) >= 0 && (j-k) >= 0; ++k) {
					// left and down
					if (V[i][j-k] == '#') {
						t += sum(i-k, i-k, j-k+1, j);
					}
					if (V[i-k][j] == '#') {
						t += sum(i-k+1, i-1, j-k, j-k);
					}
				}
			}
		}
	}
	cout << t << endl;

	return 0;
}