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 <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include<climits>
#include <string>
#include <map>
#include <set>
#include <list>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

/////////////////////////////////////////////////////
#define isIn(A,B) (0<=A&&A<H&&0<=B&&B<W)

ll H,W,MAX;
int coin[3333][3333];
ll bS[333][333],bSB[333][333];
ll S[3333][3333],BS[3333][3333];
ll ans;
ll i,j,k;

int main(){
    scanf("%lld%lld",&H,&W);
    MAX=H>W?H:W;
    fornum(i,0,H){
        char str[333];
        scanf("%s",str);
        fornum(j,0,W){
            if(str[j]=='#'){
                coin[i+1000][j+1000]=1;   
            }
        }
    }
    
    fornum(i,1,2000){
        fornum(j,1,2000){
            //BS[i+j+1000]++;
            //S[W+i-j-1+1000]++;
            BS[i][j]=BS[i-1][j-1]+(coin[i][j]?1:0);
            S[i][W-j+1999]=S[i-1][W-j+2000]+(coin[i][W-j+1999]?1:0);
        }
    }
    /*
    fornum(i,0,H){
        fornum(j,0,W){
            printf("%lld:%lld ",BS[i+1000][j+1000],S[i+1000][j+1000]);
        }
        printf("\n");
    }*/

    fornum(i,0,H){
        fornum(j,0,W){
            for(k=1;k<MAX*2;k++){
                if(coin[i+k+1000][j+1000]&&coin[i+1000][j+k+1000]){
                    ans+=S[i+1000][j-k+1000]-S[i-k+999][j+1001];
                    //printf("a%lld,%lld,%lld:%lld %lld\n",i,j,k,S[i+1000][j-k+1000],S[i-k+999][j+1001]);
                }
                if(coin[i-k+1000][j+1000]&&coin[i+1000][j-k+1000]){
                     ans+=S[i+k+1000][j+1000]-S[i+999][j+k+1001];
                     //printf("b%lld,%lld,%lld:%lld %lld\n",i,j,k,S[i+k+1000][j+1000],S[i+999][j+k+1001]);
                     //cout<<"a";
                    //ans+=BS[i+j+k+1000];
                }
                if(coin[i-k+1000][j+1000]&&coin[i+1000][j+k+1000]){
                    //ans+=S[W+i-j-1+k+1000];
                    //cout<<"b";
                    ans+=BS[i+k+999][j+999]-BS[i+1000][j-k+1000];
                    //printf("c%lld,%lld,%lld:%lld %lld\n",i,j,k,BS[i+k+1000][j+1000],BS[i+999][j-k+999]);
                }
                if(coin[i+k+1000][j+1000]&&coin[i+1000][j-k+1000]){
                    ans+=BS[i+999][j+k+999]-BS[i-k+1000][j+1000];
                    //printf("d%lld,%lld,%lld:%lld %lld\n",i,j,k,BS[i+1000][j+k+1000],BS[i-k+999][j+999]);
                    //cout<<"c";
                    //ans+=S[W+i-j-1-k+1000];
                }
            }
        }
    }

    printf("%lld\n",ans);
    
    return 0;
}