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 <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

long long sum[2100][2100];

int check(int i, int j, const vector<string> &fi) {
    int n = (int)fi.size();
    int m = (int)fi[0].size();
    if (i < 0 || i >= n || j < 0 || j >= m) return 0;
    if (fi[i][j] == '#') return 1;
    else return 0;
}

long long solve(vector<string> fi) {
    // sum[a][b] := マス (i, j) であって i+j = a, i <= b を満たす範囲内にある黒マスの個数 (斜め累積和)
    memset(sum, 0, sizeof(sum));
    int n = (int)fi.size();
    int m = (int)fi[0].size();
    for (int ij = 0; ij < n+m-1; ++ij) {
        sum[ij][0] = 0;
        for (int i = 0; i < (n+m)*3; ++i) {
            int j = ij - i;
            int add = 0;
            if (i >= 0 && i < n && j >= 0 && j < m && fi[i][j] == '#') add = 1;
            sum[ij][i+1] = sum[ij][i] + add;
        }
    }
    
    long long res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (fi[i][j] != '#') continue;
            for (int k = 1; k < n+m; ++k) {
                int i2 = i + k;
                int j2 = j - k;
                if (i2 < 0 || i2 >= n || j2 < 0 || j2 >= m) continue;
                if (fi[i2][j2] != '#') continue;
                
                // 対辺が左上方向にあるもの
                {
                    int ij = i+j - k*2;
                    if (ij >= 0) {
                        if (check(i-k, j-k, fi)) ++res; // 直角二等辺三角形
                        if (check(i, j-k*2, fi)) ++res; // 直角二等辺三角形
                        
                        int a = max(i-k+1, 0);
                        int b = max(i, 0);
                        if (a <= b) res += (sum[ij][b] - sum[ij][a]) * 2; // それ以外
                    }
                }
                
                // 対辺が右下方向にあるもの
                {
                    int ij = i+j + k*2;
                    if (ij <= n+m-2) {
                        if (check(i+k, j+k, fi)) ++res; // 直角二等辺三角形
                        if (check(i+k*2, j, fi)) ++res; // 直角二等辺三角形
                        
                        int a = i+k+1;
                        int b = i+k*2;
                        res += (sum[ij][b] - sum[ij][a]) * 2; // それ以外
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> input(H);
    for (int i = 0; i < H; ++i) cin >> input[i];
        
    long long res = 0;
    res += solve(input);

    // 盤面を左右反転
    for (int i = 0; i < H; ++i) reverse(input[i].begin(), input[i].end());
    res += solve(input);
        
    cout << res / 2 << endl;
}