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 MA = 1000;

bool exi[1000][1000];

int rsum[1000][1000], csum[1000][1000];

vector<int> rs[1000], cs[1000];

char ch[330][330];
int H, W;

void input(){
	scanf("%d%d", &H, &W);
	for(int i = 0; i < H; ++i){
		scanf("%s", ch[i]);
	}
}

long long solve(){
	for(int i = 0; i < H; ++i){
		for(int j = 0; j < W; ++j){
			if(ch[i][j] == '#'){
				int a = i + j + 1;
				int b = i - j + W + 1;
				exi[a][b] = true;
			}
		}
	}
	for(int i = 0; i < MA; ++i){
		for(int j = 1; j < MA; ++j){
			rsum[i][j] = rsum[i][j - 1];
			if(exi[i][j]){
				rsum[i][j]++;
				rs[i].push_back(j);
				cs[j].push_back(i);
			}
		}
	}
	for(int j = 0; j < MA; ++j){
		for(int i = 1; i < MA; ++i){
			csum[i][j] = csum[i - 1][j];
			if(exi[i][j]) csum[i][j]++;
		}
	}
	long long ans = 0;
	long long right = 0;
	for(int i = 0; i < MA; ++i){
		for(int j = 0; j < rs[i].size(); ++j){
			for(int k = j + 1; k < rs[i].size(); ++k){
				int d = rs[i][k] - rs[i][j];
				int i2 = i - d;
				if(i2 >= 0){
					ans += rsum[i2][rs[i][k]] - rsum[i2][rs[i][j] - 1];
					if(exi[i2][rs[i][k]]) right++;
					if(exi[i2][rs[i][j]]) right++;
				}
				i2 = i + d;
				if(i2 < MA){
					ans += rsum[i2][rs[i][k]] - rsum[i2][rs[i][j] - 1];
					if(exi[i2][rs[i][k]]) right++;
					if(exi[i2][rs[i][j]]) right++;
				}
			}
		}
	}
	for(int j = 0; j < MA; ++j){
		for(int x = 0; x < cs[j].size(); ++x){
			for(int y = x + 1; y < cs[j].size(); ++y){
				int l = cs[j][x], r = cs[j][y];
				int d = r - l;
				int j2 = j - d;
				if(j2 >= 0){
					ans += csum[r][j2] - csum[l - 1][j2];
				}
				j2 = j + d;
				if(j2 < MA){
					ans += csum[r][j2] - csum[l - 1][j2];
				}
			}
		}
	}
	return ans - right;
}

int main(){
	input();
	long long ans = solve();
	printf("%lld\n", ans);
	return 0;
}