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;
using ll = long long;

ll solve() {
    ll H, W;
    cin >> H >> W;
    ll N = H + W + 2;
    vector<vector<ll>> S(N, vector<ll>(N));
    string s;
    for ( int h = 0; h < H; h++ ) {
        cin >> s;
        for ( int w = 0; w < W; w++ ) {
            if ( s[w] == '#' ) {
                S[h+W-w+1][h+w+1] = 1;
            }
        }
    }

    auto count1 = [](ll N, vector<vector<ll>>& s,bool border) {
        vector<vector<ll>> pt(N);
        vector<vector<ll>> cs(N,vector<ll>(N));
        for ( int i = 0; i < N; i++ ) {
            for ( int j = 1; j < N; j++ ) {
                if ( s[i][j] ) pt[i].push_back(j);
                cs[i][j] = cs[i][j-1] + s[i][j];
            }
        }
        ll c = 0;
        for ( int i = 0; i < N; i++ ) {
            for ( int j1 = 0; j1 < pt[i].size(); j1++ ) {
                for ( int j2 = j1+1; j2 < pt[i].size(); j2++ ) {
                    int p1 = pt[i][j1], p2 = pt[i][j2];
                    int d = p2 - p1;
                    int dd = border ? 0 : 1;
                    if ( i - d >= 0 && p1-1+dd < p2-dd) {
                        c += (ll)(cs[i-d][p2-dd] - cs[i-d][p1-1+dd]);
                    }
                    if ( i + d < N && p1-1+dd < p2-dd ) {
                        c += (ll)(cs[i+d][p2-dd] - cs[i+d][p1-1+dd]);
                    }
                }
            }
        }
        return c;
    };

    ll ans = 0;
    ans += count1(N, S, true);
    for ( int i = 0; i < N; i++ ) {
        for ( int j = i+1; j < N; j++ ) {
            swap(S[i][j],S[j][i]);
        }
    }
    ans += count1(N, S, false);
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}