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;

int main(){
    int h, w;
    cin >> h >> w;

    vector<string> s(h), rs(h);
    for(int i=0; i<h; i++){
        string a;
        cin >> a;
        s[i] = a;
        reverse(a.begin(),a.end());
        rs[i] = a;
    }

    // +45/-45 degree direction
    vector<vector<int>> ne(h+w, vector<int>(w+1)), nw(h+w, vector<int>(w+1));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if( s[i][j] == '#') ne[i+j][j+1] = 1;
            if(rs[i][j] == '#') nw[i+j][(w-1)-j+1] = 1;
        }
    }
    // cumulative sum
    for(int i=0; i<h+w; i++){
        for(int j=0; j+1<=w; j++){
            ne[i][j+1] += ne[i][j];
            nw[i][j+1] += nw[i][j];
        }
    }

    long long int ans = 0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            //cout << "(" << i << "," << j << ")" << endl;
            for(int k=1; k<h+w; k++){
                //cout << k << " : ";

                if(i+k < h 
                && j+k < w 
                && s[i+k][j] == '#' 
                && s[i][j+k] == '#'
                && i+j-k >= 0) ans += ne[i+j-k][j] - ne[i+j-k][max(0,j-k)];
                //cout << ans << " ";

                if(i-k >= 0 
                && j-k >= 0
                && s[i-k][j] == '#'
                && s[i][j-k] == '#'
                && i+j+k < h+w) ans += ne[i+j+k][min(j+k+1,w)] - ne[i+j+k][j+1];
                //cout << ans << " ";

                if(i+k <  h 
                && j-k >= 0
                && s[i+k][j] == '#'
                && s[i][j-k] == '#'
                && i+((w-1)-j)-k >= 0)  ans += nw[i+((w-1)-j)-k][min(j+k,w)] - nw[i+((w-1)-j)-k][j];
                //cout << ans << " ";

                if(i-k >= 0 
                && j+k <  w
                && s[i-k][j] == '#'
                && s[i][j+k] == '#'
                && i+((w-1)-j)+k < h+w) ans += nw[i+((w-1)-j)+k][j+1] - nw[i+((w-1)-j)+k][max(0,j-k+1)];
                //cout << ans << endl;
            }
        }
    }
    cout << ans << endl;
    return 0;
}