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 fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

int h, w, pref[905][905];

long long sum = 0;

char a[905][905], b[905][905];

bool check(int x, int y) {
    if(x >= 1 && x <= h && y >= 1 && y <= w && a[x][y] == '#') return 1;
    return 0;
}

void solve() {
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            pref[i][j] = 0;
            if(a[i][j] == '#')
                pref[i][j] = 1;
        }
    }
    for(int i = 1; i <= 3 * h; i++) {
        for(int j = 1; j <= 3 * w; j++) {
            if(i > h || j > w)
                pref[i][j] = 0;
            pref[i][j] += pref[i - 1][j - 1];
        }
    }
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            if(a[i][j] == '.') continue;
            for(int range = 1; range <= max(h, w); range++) {
                if(check(i + range, j + range))
                    sum = sum + pref[i + 2 * range - 1][j - 1] - pref[i + range - 1][max(j - range - 1, 0)];
            }
        }
    }
}

void rot() {
    for(int j = 1; j <= w; j++) {
        int cnt = 1;
        for(int i = h; i >= 1; i--) {
            b[j][cnt] = a[i][j];
            cnt++;
        }
    }
    swap(w, h);
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++)
            a[i][j] = b[i][j];
    }
}

int main() {
    scanf("%d%d", &h, &w);
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++)
            scanf(" %c", &a[i][j]);
    }
    solve();
    rot(); solve();
    rot(); solve();
    rot(); solve();
    printf("%lld", sum);
}