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;
const int MAXN = 305, OFF = 305;

int N, M, ans;
int pst[2*MAXN][MAXN], psk[2*MAXN][MAXN];
vector<int> tambah[2*MAXN], kurang[2*MAXN];

int solve(int R, int C, vector<vector<char>> arr, int corner) {
	vector<vector<int>> ps(R+C+5, vector<int>(R+5, 0));
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (arr[i][j] == '#') {
				ps[i+j][i] = ps[i+j][i-1]+1;
			} else {
				ps[i+j][i] = ps[i+j][i-1];
			}
		}
	}
	
	int ret = 0;
	for (int i = 2; i <= R+C; i++) {
		for (int r1 = max(1, i-C); r1 <= min(R, i-1); r1++) {
			for (int r2 = r1+1; r2 <= min(R, i-1); r2++) {
				int c1 = i-r1, c2 = i-r2;
				if (arr[r1][c1] != '#' || arr[r2][c2] != '#') continue;
				int dist = r2-r1 + c1-c2;
				assert(dist > 0);
				if (i-dist >= 2) {
					int l = max(0, r2-dist-corner);
					int r = min(min(R, i-dist-1), r1-1+corner);
					ret += ps[i-dist][r]-ps[i-dist][l];
					//~ if (r1 == 2 && r2 == 3) cerr << r << " " << ps[i-dist][l] << " " << ps[i-dist][r] << endl;
					//~ if (ps[i-dist][r]-ps[i-dist][l] != 0) cerr << r1 << " " << r2 << endl;
				}
				if (i+dist <= R+C) {
					int l = max(0, r2-corner);
					int r = min(min(R, i+dist-1), r1+dist-1+corner);
					ret += ps[i+dist][r]-ps[i+dist][l];
					//~ if (ps[i+dist][r]-ps[i+dist][l] != 0) cerr << r1 << " " << r2 << endl;
				}
			}
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin >> N >> M;
	vector<vector<char>> arr(N+5, vector<char>(M+5));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
		}
	}
	
	int ans = solve(N, M, arr, 1);
	
	vector<vector<char>> rotated(M+5, vector<char>(N+5));
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			rotated[i][j] = arr[N+1-j][i];
		}
	}
	ans += solve(M, N, rotated, 0);
	
	cout << ans << "\n";
}