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;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;

signed main(){
    int h, w;
    cin >> h >> w;
    array<bitset<601>, 601> v;
    vector<pair<int,int>> p;
    for(int i = 0; i < h; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < w; ++j)
            if(s[j] == '#'){
                v[i + j].set(i - j + 300);
                p.emplace_back(i + j, i - j + 300);
            }
    }

    vector<vector<int>> r(602, vector<int>(602));
    for(int i = 0; i < 601; ++i)
        for(int j = 0; j < 601; ++j)
            r[i + 1][j + 1] = v[i][j];
    for(int i = 0; i < 602; ++i)
        for(int j = 1; j < 602; ++j)
            r[i][j] += r[i][j - 1];
    for(int j = 0; j < 602; ++j)
        for(int i = 1; i < 602; ++i)
            r[i][j] += r[i - 1][j];

    i64 ans = 0;

    for(auto& elm : p){
        int x, y;
        tie(x, y) = elm;
        for(int d = 1; d <= 600; ++d){
            if(x + d <= 600 && y + d <= 600 && v[x + d][y])
                ans += r[x + 1][y + d] + r[x + d + 1][y + d + 1] - r[x + 1][y + d + 1] - r[x + d + 1][y + d];
            if(x + d <= 600 && y - d >= 0 && v[x + d][y])
                ans += r[x][y - d] + r[x + d][y - d + 1] - r[x][y - d + 1] - r[x + d][y - d];

            if(y + d <= 600 && x + d <= 600 && v[x][y + d])
                ans += r[x + d][y] + r[x + d + 1][y + d] - r[x + d][y + d] - r[x + d + 1][y];
            if(y + d <= 600 && x - d >= 0 && v[x][y + d])
                ans += r[x - d][y + 1] + r[x - d + 1][y + d + 1] - r[x - d][y + d + 1] - r[x - d + 1][y + 1];
        }
    }
    cout << ans << endl;
}