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 rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;


int h,w;
int H=430,W=430;
int a[310][310];

int b[2][450][450];

ll bw[2][450][450],bh[2][450][450];

void convert(){
  int t = (w-1)/2;
  rep(x,0,w) rep(y,0,h) if((x+y)%2 == 0){
    if(a[y][x]==1){
      b[0][(-x+y)/2+t+1][(x+y)/2+1] = 1;
      bw[0][(-x+y)/2+t+1][(x+y)/2+1] = 1;
      bh[0][(-x+y)/2+t+1][(x+y)/2+1] = 1;
    }
  }else{
    if(a[y][x]==1){
      b[1][(-x+1+y)/2+t][(x+1+y)/2] = 1;
      bw[1][(-x+1+y)/2+t][(x+1+y)/2] = 1;
      bh[1][(-x+1+y)/2+t][(x+1+y)/2] = 1;
    }
  }
  rep(i,0,H) rep(j,0,W-1) rep(k,0,2){
    bw[k][i][j+1] += bw[k][i][j];
  }
  rep(i,0,W) rep(j,0,H-1) rep(k,0,2){
    bh[k][j+1][i] += bh[k][j][i];
  }
}

int main(){
  cin >> h >> w;
  string s;
  rep(i,0,h){
    cin >> s;
    rep(j,0,w) {
      if(s[j]=='#') a[i][j] = 1;
    }
  }
  convert();

  ll n=0;

  rep(k,1,H){
    rep(i,1,H){
      rep(j,1,W){
        if(j+k>=H)break;
        rep(l,0,2){
          if(b[l][i][j]==1 && b[l][i][j+k]==1){
            if(i-k>=0) n += bw[l][i-k][j+k]-bw[l][i-k][j-1];
            if(i+k<W) n += bw[l][i+k][j+k]-bw[l][i+k][j-1];
          }
        }
      }
    }
  }
  rep(k,1,H){
    rep(i,1,H){
      rep(j,1,W){
        if(i+k>=H)break;
        rep(l,0,2){
          if(b[l][i][j]==1 && b[l][i+k][j]==1){
            if(j-k>=0) n += bh[l][i+k-1][j-k]-bh[l][i][j-k];
            if(j+k<W) n += bh[l][i+k-1][j+k]-bh[l][i][j+k];
          }
        }
      }
    }
  }

  cout << n << endl;

  return 0;
}