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 endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 10);
const int OFFSET = 302;

int n, m;
string t[MAXN];

void read()
{
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		cin >> t[i];
}

int rs[MAXN][MAXN], cs[MAXN][MAXN];
vector<int> on_row[MAXN], on_col[MAXN];

void solve()
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(t[i][j] == '#')
			{
				int x = i + j + 3, y = i - j + OFFSET + 3;
				on_col[y].push_back(x);
				on_row[x].push_back(y);
				rs[x][y] = 1;
				cs[x][y] = 1;
			}

	for(int i = 0; i < MAXN; i++)
	{
		sort(on_col[i].begin(), on_col[i].end());
		sort(on_row[i].begin(), on_row[i].end());
	}

	for(int i = 1; i < MAXN; i++)
		for(int j = 0; j < MAXN; j++)
			cs[i][j] += cs[i - 1][j];

	for(int i = 0; i < MAXN; i++)
		for(int j = 1; j < MAXN; j++)
			rs[i][j] += rs[i][j - 1];

	int64_t answer = 0;
	for(int rw = 0; rw < MAXN; rw++)
		for(int p = 0; p < (int)on_row[rw].size(); p++)
			for(int q = p + 1; q < (int)on_row[rw].size(); q++)
				for(int d = -1; d <= 1; d += 2)
				{
					int x = rw + d * (on_row[rw][q] - on_row[rw][p]);
					if(x >= 0 && x < MAXN) 
						answer += rs[x][on_row[rw][q]] - rs[x][on_row[rw][p] - 1];
				}
	
	for(int cl = 0; cl < MAXN; cl++)
		for(int p = 0; p < (int)on_col[cl].size(); p++)
			for(int q = p + 1; q < (int)on_col[cl].size(); q++)
				for(int d = -1; d <= 1; d += 2)
				{
					int x = cl + d * (on_col[cl][q] - on_col[cl][p]);
					if(x >= 0 && x < MAXN) 
						answer += cs[on_col[cl][q] - 1][x] - cs[on_col[cl][p]][x];
				}

	cout << answer << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}