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>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
    ost<<"{"<<p.first<<","<<p.second<<"}";
    return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
    ost<<"{";
    for(int i=0;i<v.size();i++){
        if(i)ost<<",";
        ost<<v[i];
    }
    ost<<"}";
    return ost;
}

inline int topbit(unsigned long long x){
    return x?63-__builtin_clzll(x):-1;
}

inline int popcount(unsigned long long x){
    return __builtin_popcountll(x);
}

inline int parity(unsigned long long x){
    return __builtin_parity(x);
}

int H,W;
char fld[333][333];

const int B=1000;
int acc[2222][2222];
int solve(){
    memset(acc,0,sizeof(acc));
    rep(i,H)rep(j,W){
        if(fld[i][j]=='#')acc[i+B][j+B]++;
    }

    rep(i,2222)rep(j,2222){
        if(i&&j)acc[i][j]+=acc[i-1][j-1];
    }

    int ret=0;
    rep(i,H)rep(j,W){
        if(fld[i][j]=='.')continue;
        for(int t=1;;t++){
            int ii=i+t;
            int jj=j+t;
            if(ii>=H||jj>=W)break;
            if(fld[ii][jj]=='.')continue;
            ret+=acc[ii-t+B][jj+t+B]-acc[ii-2*t-1+B][jj-1+B];
            ret+=acc[ii+t+B][jj-t+B]-acc[ii-1+B][jj-2*t-1+B];
        }
    }
    return ret;
}

bool ex(int y,int x){
    if(y<0||y>=H||x<0||x>=W)return false;
    return fld[y][x]=='#';
}

signed main(){
    cin>>H>>W;
    rep(i,H)cin>>fld[i];

    int ans=solve();
    rep(i,H)reverse(fld[i],fld[i]+W);
    ans+=solve();

    rep(i,H)rep(j,W){
        if(fld[i][j]=='.')continue;
        for(int t=1;;t++){
            int ii=i+t;
            int jj=j+t;
            if(ii>=H||jj>=W)break;
            if(fld[ii][jj]=='.')continue;
            if(ex(ii-t,jj+t))ans--;
            if(ex(ii-2*t,jj))ans--;
            if(ex(ii+t,jj-t))ans--;
            if(ex(ii,jj-2*t))ans--;
        }
    }
    cout<<ans<<endl;
    return 0;
}