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:
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
// #define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
 
const int N=303;
vector<string> f;
int p[N][N];
int n,m,s;
void rot(){
    vector<string> tmp(m,string(n,'?'));
    forn(i,n)forn(j,m)tmp[j][n-1-i]=f[i][j];
    f=tmp;
    swap(n,m);
}
bool g(int x,int y){
    if(0<=x&&x<n&&0<=y&&y<m)return f[x][y]=='#';
    return 0;
}
int w(int x,int y){
    int delta=max(x-n+1,y-m+1);
    upx(delta,0);
    x-=delta;
    y-=delta;
    if(x<0||y<0)return 0;
    return p[x][y];
}
int h(int x1,int y1,int x2,int y2){
    return w(x2,y2)-w(x1-1,y1-1);
}
int solve(){
    int res=0;
    forn(i,n){
        forn(j,m){
            if(i&&j)p[i][j]=p[i-1][j-1];
            else p[i][j]=0;
            if(g(i,j))++p[i][j];
        }
    }
    forn(i,n)forn(j,m)if(g(i,j))for(int d=1;d+d<=s;d++)if(g(i+d,j+d))res+=h(i-d+1,j+d+1,i,j+d+d);
    return res;
}
int32_t main(){
    cin>>n>>m;
    f.resize(n);
    s=n+m;
    forn(i,n)cin>>f[i];
    int ans=0;
    forn(i,4){
        ans+=solve();
        rot();
    }
    cout<<ans<<'\n';
    return 0;
}