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 <stdio.h>

int t1,t2;

int h,w;
char ch;

bool coin[605][605];
int psa1[605][605];
int psa2[605][605];
int ans=0;

int main()
{
    #ifdef NOT_DMOJ
    freopen("data.txt","r",stdin);
    #endif // NOT_DMOJ
    scanf("%d%d",&h,&w);
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            scanf(" %c",&ch);
            if (ch=='.') continue;
            // rotate by 45
            // (i,j) |-> (i-j,i+j)
            coin[i-j+301][i+j+1]=1;
            psa1[i-j+301][i+j+1]=1;
            psa2[i-j+301][i+j+1]=1;
            //printf("coin %d %d\n",i-j+300,i+j);
        }
    }
    for (int i=0; i<602; i++) {
        for (int j=0; j<602; j++) {
            psa1[i][j+1]+=psa1[i][j];
            psa2[i+1][j]+=psa2[i][j];
        }
    }
    for (int i=1; i<602; i++) {
        for (int j=(i%2); j<602; j+=2) {
            for (int k=j+2; k<602; k+=2) {
                if (coin[i][j] && coin[i][k]) {
                    // (i,j) (i,k)
                    // want coin at (i +- (k-j),x)
                    // where j <= x <= k
                    // avoid double counting weirdly
                    t1=ans;
                    if (i+k-j<602) ans+=psa1[i+k-j][k-1]-psa1[i+k-j][j];
                    if (i-k+j>0) ans+=psa1[i-k+j][k-1]-psa1[i-k+j][j];
                    //if (t1!=ans) printf("%d %d %d %d %d\n",ans,i-301,j-1,i-301,k-1);
                }
                if (coin[j][i] && coin[k][i]) {
                    // (j,i) (k,i)
                    // want coin at (x,i +- (k-j))
                    // where j <= x <= k
                    t1=ans;
                    if (i+k-j<602) ans+=psa2[k][i+k-j]-psa2[j-1][i+k-j];
                    if (i-k+j>0) ans+=psa2[k][i-k+j]-psa2[j-1][i-k+j];
                    //if (t1!=ans) printf("%d %d %d %d %d\n",ans,j-301,i-1,k-301,i-1);
                }
            }
        }
    }
    printf("%d\n",ans);
}