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 <algorithm>

using namespace std;

char s[300][301];
int sum1[600][301];
int sum2[600][301];

int get1(int p, int l, int r) {
    l = max(l, 0);
    r = min(r + 1, 300);
    
    if (p < 0 || p >= 600) return 0;
    
    return sum1[p][r] - sum1[p][l];
}

int get2(int p, int l, int r) {
    p += 300;
    l = max(l, 0);
    r = min(r + 1, 300);
    
    if (p < 0 || p >= 600) return 0;
    
    return sum2[p][r] - sum2[p][l];
}

int main() {
    int h, w, i, j, k;
    long long ans = 0;
    
    scanf("%d %d", &h, &w);
    
    for (i = 0; i < h; i++) scanf("%s", s[i]);
    
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (s[i][j] == '#') {
                sum1[i + j][i + 1]++;
                sum2[i - j + 300][i + 1]++;
            }
        }
    }
    
    for (i = 0; i < 600; i++) {
        for (j = 1; j <= 300; j++) {
            sum1[i][j] += sum1[i][j - 1];
            sum2[i][j] += sum2[i][j - 1];
        }
    }
    
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (s[i][j] == '.') continue;
            
            for (k = 1; ; k++) {
                int x = i + k;
                int y = j - k;
                
                if (x >= h || y < 0) break;
                if (s[x][y] == '.') continue;
                
                ans += get1(i + j - k * 2, i - k, i);
                ans += get1(i + j + k * 2, x, x + k);
            }
            
            for (k = 1; ; k++) {
                int x = i + k;
                int y = j + k;
                
                if (x >= h || y >= w) break;
                if (s[x][y] == '.') continue;
                
                ans += get2(i - j - k * 2, i - k, i);
                ans += get2(i - j + k * 2, x, x + k);
            }
            
            for (k = 1; i + k * 2 < h; k++) {
                if (s[i + k * 2][j] == '.') continue;
                
                if (j - k >= 0 && s[i + k][j - k] == '#') ans--;
                if (j + k < w && s[i + k][j + k] == '#') ans--;
            }
            
            for (k = 1; j + k * 2 < w; k++) {
                if (s[i][j + k * 2] == '.') continue;
                
                if (i - k >= 0 && s[i - k][j + k] == '#') ans--;
                if (i + k < h && s[i + k][j + k] == '#') ans--;
            }
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}