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;
string s[302];
int a[302][302];
int f[302][302];
int n, m;
int calc(int r, int c, int len) {
    if (len < 0) {
        return 0;
    }
    int lsum = 0;
    if (r - 1 > 0 && c - 1 > 0) {
        lsum += f[r - 1][c - 1];
    }
    if (r + len >= n || c + len >= m) {
        len = min(n - r,  m - c);
    }
    int rsum = 0;
    if (r + len >= 1 && c + len >= 1) {
        rsum = f[r + len][c + len];
    }
    return rsum - lsum;
}

void go(int r, int c, long long &ans, int tp) {
    int len = min(n - r, m - c);
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j <= len; j++) {
            if (a[r + i][c + i] == 0) continue;
            if (a[r + j][c + j] == 0) continue;
            ans += calc(r + j - 2 * (j - i) + tp, c + j + tp, j - i - 2 * tp);
            ans += calc(r + j + tp, c + j - 2 * (j - i) + tp, j - i - 2 * tp);

        }
    }
}

void solve(long long &ans, int tp) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = a[i][j] + f[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        go(i, 1, ans, tp);
    }
    for (int i = 2; i <= m; i++) {
        go(1, i, ans, tp);
    }

}
int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j - 1] == '#') a[i][j] = 1;
        }
    }
    long long ans = 0;
    solve(ans, 0);
    for (int i = 1; i <= n; i++) {
        reverse(a[i] + 1, a[i] + m + 1);
    }
    solve(ans, 1);
    cout << ans << "\n";
    return 0;
}