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 rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
int a[610][610];
int sumx[610][610],sumy[610][610];
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int h,w,ans=0,twice=0;
    cin>>h>>w;
    char s[310][310];
    rep(i,h){
        rep(j,w){
            cin>>s[i][j];
            if(s[i][j]=='#'){
                int x=i+300,y=j;
                a[x+y-300][x-y]=1;
            }
        }
    }
    rep(i,600){
        sumx[i][0]=a[i][0];
        rep(j,599){
            sumx[i][j+1]=sumx[i][j]+a[i][j+1];
        }
    }
    rep(j,600){
        sumy[0][j]=a[0][j];
        rep(i,599){
            sumy[i+1][j]=sumy[i][j]+a[i+1][j];
        }
    }
    rep(x,600){
        rep(y1,600){
            rep(y2,600){
                if(a[x][y1]&&a[x][y2]&&y2>y1){
                    int d=y2-y1;
                    if(x-d>=0){
                        ans+=sumx[x-d][y2]-(y1?sumx[x-d][y1-1]:0);
                        twice+=a[x-d][y2];
                        twice+=a[x-d][y1];
                    }
                    if(x+d<600){
                        ans+=sumx[x+d][y2]-(y1?sumx[x+d][y1-1]:0);
                        twice+=a[x+d][y2];
                        twice+=a[x+d][y1];
                    }
                }
            }
        }
    }
    rep(y,600){
        rep(x1,600){
            rep(x2,600){
                if(a[x1][y]&&a[x2][y]&&x2>x1){
                    int d=x2-x1;
                    if(y-d>=0){
                        ans+=sumy[x2][y-d]-(x1?sumy[x1-1][y-d]:0);
                        twice+=a[x2][y-d];
                        twice+=a[x1][y-d];
                    }
                    if(y+d<600){
                        ans+=sumy[x2][y+d]-(x1?sumy[x1-1][y+d]:0);
                        twice+=a[x2][y+d];
                        twice+=a[x1][y+d];
                    }
                }
            }
        }
    }
    cout<<ans-twice/2<<endl;
    return 0;
}