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<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int h;
int w;

vector<pair<int, int> > v;

int calct[1300][1300];
int calcy[1300][1300];

#define BASE 610

vector<int> vx[1300];
vector<int> vy[1300];

char buf[500];

int main() {
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		scanf("%s", buf);
		for (int j = 0; j < w; j++) {
			if (buf[j] == '#') {
				v.push_back(make_pair(i + j, i - j));
				calct[i + j+BASE][i - j+BASE]++;
				calcy[i + j+BASE][i - j+BASE]++;
				vx[i + j + BASE].push_back(i - j+BASE);
				vy[i - j + BASE].push_back(i + j+BASE);
			}
		}
	}
	for (int i = 0; i < 1300; i++) {
		for (int j = 1; j <1300; j++) {
			calcy[i][j] += calcy[i][j - 1];
		}
	}
	for (int j = 0; j < 1300; j++) {
		for (int i = 1; i < 1300; i++) {
			calct[i][j] += calct[i - 1][j];
		}
	}
	long long int way = 0;
	for (int i = 0; i < 1300; i++) {
		sort(vx[i].begin(), vx[i].end());
		for (int j = 0; j < vx[i].size(); j++) {
			for (int k = j + 1; k < vx[i].size(); k++) {
				int dif = vx[i][k] - vx[i][j];
				int y1 = vx[i][j];
				int y2 = vx[i][k];
				int dir = -1;
				for (int tim = 0; tim < 2; tim++) {
					dir *= -1;
					int nex_x = i + dir*dif;
					if (nex_x >= 0 && nex_x < 1300) {
						way += calcy[nex_x][y2];
						if (y1)way -= calcy[nex_x][y1 - 1];
					}
				}
			}
		}
	}
	for (int i = 0; i < 1300; i++) {
		sort(vy[i].begin(), vy[i].end());
		for (int j = 0; j < vy[i].size(); j++) {
			for (int k = j + 1; k < vy[i].size(); k++) {
				int dif = vy[i][k] - vy[i][j];
				int x1 = vy[i][j];
				int x2 = vy[i][k];
				int dir = -1;
				for (int tim = 0; tim < 2; tim++) {
					dir *= -1;
					int nex_y = i + dir * dif;
					if (nex_y >= 0 && nex_y < 1300) {
						way += calct[x2-1][nex_y];
						way -= calct[x1][nex_y];
					}
				}
			}
		}
	}
	cout << way << endl;
	return 0;
}