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 ll long long
#define ld long double

int main() {
    int H, W;
    cin >> H >> W;
    int K = 605;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) cin >> grid[i];
    vector<vector<bool>> exist(K, vector<bool>(K, 0));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (grid[i][j] == '#') exist[i+j+1][i-j+300] = true;
        }
    }
    
    vector<vector<int>> xsum(K, vector<int>(K, 0)), ysum = xsum;
    for (int i = 0; i < K; i++) {
        if (exist[i][0]) xsum[i][0] = 1;
        for (int j = 1; j < K; j++) {
            xsum[i][j] = xsum[i][j-1];
            if (exist[i][j]) xsum[i][j]++;
        }
    }
    
    for (int j = 0; j < K; j++) {
        if (exist[0][j]) ysum[0][j] = 1;
        for (int i = 1; i < K; i++) {
            ysum[i][j] = ysum[i-1][j];
            if (exist[i][j]) ysum[i][j]++;
        }
    }
    ll ans = 0;
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            for (int k = j+1; k < K; k++) {
                if (exist[i][j] && exist[i][k]) {
                    int dist = k-j;
                    if (i+dist < K) ans += xsum[i+dist][k] - xsum[i+dist][j-1];
                    if (i-dist >= 0) ans += xsum[i-dist][k] - xsum[i-dist][j-1];
                }
            }
        }
    }
    
    for (int i = 0; i < K; i++) {
        for (int j = i+1; j < K; j++) {
            for (int k = 0; k < K; k++) {
                if (exist[i][k] && exist[j][k]) {
                    int dist = j-i;
                    if (k+dist < K) ans += ysum[j-1][k+dist] - ysum[i][k+dist];
                    if (k-dist >= 0) ans += ysum[j-1][k-dist] - ysum[i][k-dist];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}