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>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

const int dx[] = { -1,0,1,0 }, dy[] = { 0,-1,0,1 };
int N, M, K;
vector<string> F;
int C[1000][1000], PS[1000][1000];

bool valid_coord(int x, int y, bool chk = true)
{
	if(chk) return 0 < x && x <= N && 0 < y && y <= N && C[x][y];
	return 0 < x && x <= N && 0 < y && y <= N;
}

int cnt(int x1, int y1, int x2, int y2)
{
	if (!valid_coord(x1, y1, false) || !valid_coord(x2, y2, false) || x1 > x2 || y1 > y2) return 0;
	return PS[x2][y2] - PS[x1 - 1][y2] - PS[x2][y1 - 1] + PS[x1 - 1][y1 - 1];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	long long ans = 0;
	cin >> N >> M;
	F.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> F[i];
		for (int j = 0; j < M; j++) {
			C[M + i - j][i + j + 1] = F[i][j] == '#';
		}
	}
	N += M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			PS[i][j] = C[i][j] + PS[i][j - 1] + PS[i - 1][j] - PS[i - 1][j - 1];
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (valid_coord(i, j)) {
				for (int k = max(N - i, N - j); k; k--) {
					if (valid_coord(i + k, j)) {
						ans += cnt(i + 1, j - k, i + k, j - k);
						ans += cnt(i, j + k, i + k, j + k);
					}
					if (valid_coord(i, j + k)) {
						ans += cnt(i - k, j + 1, i - k, j + k - 1);
						ans += cnt(i + k, j, i + k, j + k);
					}
					ans -= valid_coord(i + k, j) && valid_coord(i, j + k);
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}