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 <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int H, W;

char ch[333][333];

int S[777][777], B[333][333];

long long Solve() {
    memset(S, 0, sizeof S);
    for(int XY = 2; XY <= H + W; XY++)
        for(int X = max(XY - W, 1); X <= min(H, XY - 1); X++)
            S[XY][X] = S[XY][X - 1] + B[X][XY - X];
    long long ans = 0;
    for(int X2 = 1; X2 <= H; X2++)
        for(int Y2 = 1; Y2 <= W; Y2++) if(B[X2][Y2])
            for(int a = 1; X2 - a > 0 && Y2 + a <= W && X2 + Y2 + 2 * a <= H + W; a++) if(B[X2 - a][Y2 + a]) {
                int s = X2 + Y2 + 2 * a;
                int l = max(s - W, 1), r = min(H, s - 1);
                l = max(l, X2 + 1);
                r = min(r, a + X2 - 1);
                ans += S[s][r] - S[s][l - 1];
            }
    return ans;
}

long long check() {
    long long ans = 0;
    for(int i = 1; i <= W; i++)
        for(int l = 1; l <= H; l++) if(B[l][i])
            for(int r = l + 2; r <= H; r += 2) if(B[r][i]) {
                int t = (r - l) / 2;
                if(i - t > 0) ans += B[l + t][i - t];
                if(i + t <= W) ans += B[l + t][i + t];
            }
    for(int i = 1; i <= H; i++)
        for(int l = 1; l <= W; l++) if(B[i][l])
            for(int r = l + 2; r <= W; r += 2) if(B[i][r]) {
                int t = (r - l) / 2;
                if(i - t > 0) ans += B[i - t][l + t];
                if(i + t <= H) ans += B[i + t][l + t];
            }
    return ans;
}

int main() {
    scanf("%d%d", &H, &W);
    for(int i = 1; i <= H; i++) {
        scanf("%s", ch[i] + 1);
        for(int j = 1; j <= W; j++)
            B[j][i] = ch[i][j] == '#';
    }
    swap(H, W);
    long long ans = check();
    ans += Solve();
    for(int i = 1; i <= H; i++)
        for(int j = 1, k = W; j < k; j++, k--)
            swap(B[i][j], B[i][k]);
    ans += Solve();
    for(int i = 1, j = H; i < j; i++, j--)
        for(int k = 1; k <= W; k++)
            swap(B[i][k], B[j][k]);
    ans += Solve();
    for(int i = 1; i <= H; i++)
        for(int j = 1, k = W; j < k; j++, k--)
            swap(B[i][j], B[i][k]);
    ans += Solve();
    printf("%lld\n", ans);
    return 0;
}