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<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

bool coinuv[600][600];
int rua[601][601];
int rub[601][601];

signed main() {
    int H, W;
    cin >> H >> W;
    rep(i, H) {
        rep(j, W) {
            char c;
            cin >> c;
            if (c == '#')coinuv[i - j + 300][i + j] = true;
        }
    }
    int ans = 0;
    rep(i, 600) {
        rep(j, 600) {
            if (coinuv[i][j]) {
                for (int k = 1; i - k >= 0; ++k) {
                    if (coinuv[i - k][j]) {
                        if (j + k < 600 && coinuv[i][j + k])ans++;
                        if (j - k >= 0 && coinuv[i][j - k])ans++;
                    }
                }
                for (int k = 1; i + k < 600; ++k) {
                    if (coinuv[i + k][j]) {
                        if (j + k < 600 && coinuv[i][j + k])ans++;
                        if (j - k >= 0 && coinuv[i][j - k])ans++;
                    }
                }
            }
        }
    }

    rep(i, 600) {
        rep(j, 600) {
            rua[i + 1][j] = rua[i][j] + coinuv[i][j];
            rub[i][j + 1] = rub[i][j] + coinuv[i][j];
        }
    }

    rep(i, 600) {
        rep(j, 600) {
            if (coinuv[i][j]) {
                for (int k = 1; i + k < 600; ++k) {
                    if (coinuv[i + k][j]) {
                        //i+1~i+k-1[j+-k]
                        if (j + k < 600)ans += rua[i + k][j + k] - rua[i + 1][j + k];
                        if (j - k >= 0)ans += rua[i + k][j - k] - rua[i + 1][j - k];
                    }
                }
                for (int k = 1; j + k < 600; ++k) {
                    if (coinuv[i][j + k]) {
                        //[i+-k]j+1~j+k-1
                        if (i + k < 600)ans += rub[i + k][j + k] - rub[i + k][j + 1];
                        if (i - k >= 0)ans += rub[i - k][j + k] - rub[i - k][j + 1];
                    }
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}