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:
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 600 + 10 ;
int n , m ;
string s[N] ;

vector <int> v1[N] , v2[N] ;
int p1[N][N] , p2[N][N] ;

ll ans ;

int main(){
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;

	cin >> n >> m ;

	for (int i = 0 ; i < n ; i ++) {
		cin >> s[i] ;

		for (int j = 0 ; j < m ; j ++) {
			if (s[i][j] == '#') {
				v1[i + j].push_back(i - j + m) ;
				p1[i + j][i - j + m + 1] ++ ;

				v2[i - j + m].push_back(i + j) ;
				p2[i - j + m][i + j + 1] ++ ;
			}
		}
	}

	for (int i = 0 ; i < N ; i ++) {
		sort(v1[i].begin() , v1[i].end()) ;
		sort(v2[i].begin() , v2[i].end()) ;

		for (int j = 1 ; j < N ; j ++) {
			p1[i][j] += p1[i][j - 1] ;
			p2[i][j] += p2[i][j - 1] ;
		}
	}

	for (int i = 0 ; i < N ; i ++) {

		for (int a = 0 ; a < _sz(v1[i]) ; a ++) {
			for (int b = a + 1 ; b < _sz(v1[i]) ; b ++) {
				int A = v1[i][a] , B = v1[i][b] ;
				int d = B - A ;

				if (i + d < N) ans += p1[i + d][B] - p1[i + d][A + 1] ;
				if (i - d >= 0) ans += p1[i - d][B] - p1[i - d][A + 1] ;
			}
		}

		for (int a = 0 ; a < _sz(v2[i]) ; a ++) {
			for (int b = a + 1 ; b < _sz(v2[i]) ; b ++) {
				int A = v2[i][a] , B = v2[i][b] ;
				int d = B - A ;

				if (i + d < N) ans += p2[i + d][B + 1] - p2[i + d][A] ;
				if (i - d >= 0) ans += p2[i - d][B + 1] - p2[i - d][A] ;
			}
		}
	}

	cout << ans << '\n' ;
}