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 <fstream>
using namespace std;
const int nmax=305;
string s;
int dL[]={-1,0,1,0};
int dC[]={0,-1,0,1};
int a[2*nmax][2*nmax];
int ss[2*nmax][2*nmax];
int n,m,t,i,j,dist,A1,A2,B1,B2,lim;
long long ans=0;
void conv()
{
    for(j=1;j<=m;j++)
        if(s[j]=='#')
    {
        a[i-j+t][i+j]=1;
    }
}
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
int man(int A1,int B1,int A2,int B2)
{
    return max(abss(A1-A2),abss(B1-B2));
}
bool ok(int A1,int B1)
{
    return (A1>=1&&A1<=2*t&&B1>=1&&B1<=2*t&&a[A1][B1]);
}
int chk(int A,int B,int D,int d1,int d2)
{
    A1=A+dL[d1]*D;B1=B+dC[d1]*D;
    A2=A+dL[d2]*D;B2=B+dC[d2]*D;
    if((!ok(A2,B2))) return 0;
    if(man(A1,B1,A2,B2)!=D)
        return 0;
    return 1;
}
int sum(int A1,int B1,int A2,int B2)
{
    if(A1<=0||A2>2*t) return 0;
    if(B1<=0||B2>2*t) return 0;
    if(A1>A2||B1>B2) return 0;
    return ss[A2][B2]-ss[A2][B1-1]-ss[A1-1][B2]+ss[A1-1][B1-1];
}
void cat(int A,int B,int D)
{
    A1=A-D;B1=B;
    if(ok(A1,B1))
    {
        ans+=1LL*sum(A1+1,B-D,A-1,B-D);
        ans+=1LL*sum(A1+1,B+D,A-1,B+D);
    }
    A1=A;B1=B-D;
    if(ok(A1,B1))
    {
        ans+=1LL*sum(A-D,B1+1,A-D,B-1);
        ans+=1LL*sum(A+D,B1+1,A+D,B-1);
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    t=max(n,m);
    for(i=1;i<=n;i++)
    {
        cin>>s;
        s=" "+s;
        conv();
    }
    for(i=1;i<=2*t;i++)
        for(j=1;j<=2*t;j++)
          ss[i][j]=ss[i-1][j]+ss[i][j-1]-ss[i-1][j-1]+a[i][j];
    for(i=1;i<=2*t;i++)
        for(j=1;j<=2*t;j++)
            if(a[i][j])
    {
        lim=max(max(i,j),max(2*t-i,2*t-j));
        for(dist=1; dist<=lim; dist++)
        {
            for(int i1=0; i1<4; i1++)
               if(ok(i+dL[i1]*dist,j+dC[i1]*dist))
                for(int i2=i1+1; i2<4; i2++)
                    ans+=1LL*chk(i,j,dist,i1,i2);
            cat(i,j,dist);
        }
    }
    cout<<ans;
    return 0;
}