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 <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

int H,W;
int board[606][606];
int tate[606][606];
int yoko[606][606];

int getTs(int i,int s,int t){
    return tate[t][i]-(s==0?0:tate[s-1][i]);
}

int getYs(int i,int s,int t){
    return yoko[i][t]-(s==0?0:yoko[i][s-1]);
}

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

  cin>>H>>W;
  vector<string> S(H);
  rep(i,H) cin>>S[i];

  rep(i,H) rep(j,W){
      if(S[i][j]=='#'){
          int x=i+j;
          int y=j-i+H-1;
          board[x][y]=1;
      }
  }

  int N=H+W;
  for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
          if(j>0)yoko[i][j]+=yoko[i][j-1];
          if(board[i][j]) yoko[i][j]++;
      }
  }
  for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
          if(j>0) tate[j][i]+=tate[j-1][i];
          if(board[j][i]) tate[j][i]++;
      }
  }

  ll ans=0;
  for(int i=0;i<N;i++){
      for(int s=0;s<N;s++) for(int t=s+1;t<N;t++){
          int l=t-s;
          if(board[i][s]&&board[i][t]){
              if(i-l>=0){
                  ans+=getYs(i-l,s,t);
                  if(board[i-l][s]) ans--;
                  if(board[i-l][t]) ans--;
              }
              if(i+l<N){
                  ans+=getYs(i+l,s,t);
                  if(board[i+l][s]) ans--;
                  if(board[i+l][t]) ans--;
              }
          }
      }
  }

  for(int i=0;i<N;i++){
      for(int s=0;s<N;s++) for(int t=s+1;t<N;t++){
          int l=t-s;
          if(board[s][i]&&board[t][i]){
              if(i-l>=0) ans+=getTs(i-l,s,t);
              if(i+l<N) ans+=getTs(i+l,s,t);
          }
      }
  }

  cout<<ans<<endl;

  return 0;
}