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>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
const int off = 300;
int n, m;
int dl[710][710], dr[710][710];
char s[310][310];
int get_dl(int idx, int l, int r) {
	if(l > r) return 0;
	if(idx < 0 || idx >= 710) return 0;
	l = max(l, 1); r = min(r, m);
	return dl[idx][r] - dl[idx][l-1];
}
int get_dr(int idx, int l, int r) {
	if(l > r) return 0;
	if(idx < 0 || idx >= 710) return 0;
	l = max(l, 1); r = min(r, m);
	return dr[idx][r] - dr[idx][l-1];
}
int get(int y, int x) {
	if(y<1 || x<1 || y>n || x>m) return 0;
	return s[y][x] == '#';
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%s", s[i]+1);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(s[i][j] == '#') {
				dl[i+j][j]++;
				dr[i-j+off][j]++;
			}
		}
	}
	for(int i=0; i<700; i++) {
		for(int j=0; j<=700; j++) {
			dl[i][j+1] += dl[i][j];
			dr[i][j+1] += dr[i][j];
		}
	}
	ll r1 = 0, r2 = 0;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(s[i][j] != '#') continue;
			for(int k=2; k<=n+m; k+=2) {
				int c11 = get_dr(i-j+off-k, j+1, j+k/2-1);
				int c12 = get_dr(i-j+off-k, j+k/2+1, j+k-1);
				int c21 = get_dl(i+j+k, j+k/2+1, j+k-1);
				int c22 = get_dl(i+j+k, j+1, j+k/2-1);
				int c31 = get_dr(i-j+off+k, j-k/2+1, j-1);
				int c32 = get_dr(i-j+off+k, j-k+1, j-k/2-1);
				int c41 = get_dl(i+j-k, j-k+1, j-k/2-1);
				int c42 = get_dl(i+j-k, j-k/2+1, j-1);
				int ru = get(i-k/2, j+k/2);
				int rd = get(i+k/2, j+k/2);
				int ld = get(i+k/2, j-k/2);
				int lu = get(i-k/2, j-k/2);
				int u = get(i-k, j);
				int r = get(i, j+k);
				int d = get(i+k, j);
				int l = get(i, j-k);
				r1 += rd * (c12 + c31);
				r1 += ld * (c22 + c41);
				r1 += lu * (c32 + c11);
				r1 += ru * (c21 + c42);
				r2 += rd * (ld + r + d);
				r2 += ld * (lu + l + d);
				r2 += lu * (ru + l + u);
				r2 += ru * (rd + r + u);
				//printf("%d %d %d %d  %d %d %d %d\n", ru,rd,ld,lu,r,d,l,u);
				//printf("i:%d, j:%d, k:%d, r1:%d, r2:%d\n", i,j,k,r1,r2);
				//printf("i:%d, j:%d, k:%d, %d %d %d %d r1:%d, r2:%d\n", i, j, k, c1,c2,c3,c4,r1,r2);
			}
		}
	}
	printf("%lld", r1 / 2 + r2 / 3);
	return 0;
}