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;

const int max_n = 303, inf = 1000111222;

int n, m;
char a[max_n][max_n];
bitset<max_n> b[max_n];
long long ans;

void proc(int x1, int y1, int x2, int y2) {
    //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " -> ";
    int x0 = 0, y0 = 0;
    if (min(y1, y2) < 0) {
        y0 = -min(y1, y2);
    }
    y1 += y0;
    y2 += y0;
    //cout << x0 << " " << y0 << " " << x1 << " " << y1 << " " << x2 << " " << y2 << ": ";
    for (int i = 0; i + x2 < n; ++i) {
        ans += ((b[i] >> y0) & (b[i + x1] >> y1) & (b[i + x2] >> y2)).count();
    }
    //cout << ans << endl;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", a[i]);
        for (int j = 0; j < m; ++j) {
            b[i][j] = (a[i][j] == '#');
        }
    }
    for (int x1 = 0; x1 < n; ++x1) {
        for (int y1 = -m + 1; y1 < m; ++y1) {
            if (x1 == 0 && y1 <= 0) {
                continue;
            }
            int l = x1 + abs(y1);
            for (int x2 = x1; x2 < n; ++x2) {
                for (int z = -1; z <= 1; z += 2) {
                    int y2 = (l - x2) * z;
                    if (abs(y1 - y2) >= m || x2 - x1 + abs(y1 - y2) != l || x2 + abs(y2) != l) {
                        continue;
                    }
                    if (x1 == x2 && y1 < y2) {
                        continue;
                    }
                    proc(x1, y1, x2, y2);
                    if (y2 == 0) {
                        break;
                    }
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}