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<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

char field[324][324];
Int lsum[323][324];
Int rsum[324][324];
Int res = 0;
Int h, w;
Int cntl(Int x, Int y){
  if(x-y < 1-w || x-y > h-1)return 0;
  if(x < 0){
    Int k = -x;
    x += k;
    y += k;
  }
  if(y < 0){
    Int k = -y;
    x += k;
    y += k;
  }
  if(x > h){
    Int k = x-h;
    x -= k;
    y -= k;
  }
  if(y > w+1){
    Int k = y-w-1;
    x -= k;
    y -= k;
  }
  return lsum[x][y];
}

Int cntr(Int x, Int y){
  if(x+y < 2 || x+y > h+w)return 0;
  if(x < 0){
    Int k = -x;
    x += k;
    y -= k;
  }
  if(y < 0){
    Int k = -y;
    x -= k;
    y += k;
  }
  if(x > h){
    Int k = x-h;
    x -= k;
    y += k;
  }
  if(y > w+1){
    Int k = y-w-1;
    x += k;
    y -= k;
  }
  return rsum[x][y];
}

int main(){
  cin >> h >> w;
  for(Int i = 1;i <= h;i++){
    for(Int j = 1;j <= w;j++){
	cin >> field[i][j];
    } 
  }
  for(Int i = 0;i <= h;i++){
    for(Int j = 0;j <= w+1;j++){
      if(i == 0 || j == 0)lsum[i][j] = 0;
      else lsum[i][j] = lsum[i-1][j-1] + (field[i][j] == '#');
      if(i == 0 || j == w+1)rsum[i][j] = 0;
      else rsum[i][j] = rsum[i-1][j+1] + (field[i][j] == '#');
    }
  }

  for(Int i = 1;i <= h;i++){
    for(Int j = 1;j <= w;j++){
      if(field[i][j] == '.')continue;
      Int xi = i+1, xj = j+1;
      for(;xi <= h && xj <= w;xi++,xj++){
	if(field[xi][xj] == '.')continue;
	res += cntl(xi+xi-i,j)-cntl(xi-1,j+j-xj-1);
	res += cntl(i,xj+xj-j) - cntl(i+i-xi-1, xj-1);
      }
      xi = i+1, xj = j-1;
      for(;xi <= h && xj >= 1;xi++,xj--){
	if(field[xi][xj] == '.')continue;
	res += cntr(xi+xi-i-1,j+1) - cntr(xi,j+j-xj);
	//	cout << i << " " << j << " " << xi << " " << xj << endl;
	//cout << xi+xi-i-1 << " " << j+1 << " " << xi << " " << j+j-xj << endl;
	//cout << cntr(xi+xi-i-1,j+1) << " "  <<  cntr(xi,j+j-xj) << endl;
	res += cntr(i-1,xj+xj-j+1) - cntr(i+i-xi,xj);
      }
    }
  }
  cout << res << endl;
  return 0;
}