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 pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n, m;
char a[444][444];
int b[444][444], hor[444][444], ver[444][444];
string s;

LL solve() {
    LL res = 0;
    forn(i, 400) {
        hor[i][0] = 0;
        forn(j, 400) {
            hor[i][j + 1] = hor[i][j] + b[i][j];
        }
    }
    forn(j, 400) {
        ver[0][j] = 0;
        forn(i, 400) {
            ver[i + 1][j] = ver[i][j] + b[i][j];
        }
    }
    forn(i, 400) {
        forn(jj, 400) forn(j, jj) {
            if (!b[i][j] || !b[i][jj]) {
                continue;
            }
            int ii = i - (jj - j);
            if (ii >= 0 && ii < 400) {
                res += hor[ii][jj + 1] - hor[ii][j];
            }
            ii = i + (jj - j);
            if (ii >= 0 && ii < 400) {
                res += hor[ii][jj + 1] - hor[ii][j];
            }
        }
    }
    forn(j, 400) {
        forn(ii, 400) forn(i, ii) {
            if (!b[i][j] || !b[ii][j]) {
                continue;
            }
            int jj = j - (ii - i);
            if (jj >= 0 && jj < 400) {
                res += ver[ii][jj] - ver[i + 1][jj];
            }
            jj = j + (ii - i);
            if (jj >= 0 && jj < 400) {
                res += ver[ii][jj] - ver[i + 1][jj];
            }
        }
    }
    return res;
}

int main() {
//    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    forn(i, n) {
        cin >> s;
        forn(j, m) {
            a[i][j] = s[j];
        }
    }
    LL ans = 0;
    forn(t, 2) {
        memset(b, 0, sizeof b);
        forn(i, n) forn(j, m) {
            if ((i + j) % 2 == t && a[i][j] == '#') {
                b[(i + j + t) / 2][(i - j + t) / 2 + 180] = 1;
            }
        }
        ans += solve();
    }
    cout << ans << endl;
    return 0;
}