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;

const int N = 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;
const int K = 300;

int n, m;
string s[N];
int sum1[K][K + K][K], sum2[K][K + K][K];

bool read() {
    if (!(cin >> n >> m))
        return false;

    for (int i = 0; i < n; ++i)
        cin >> s[i];

    return true;
}

template<typename T>
long long diag(int x1, int y1, int x2, int y2, int d, const T& f, const int sum[K][K + K][K]) {
    auto id = f(x1, y1);

    if (id < 0 || id >= K + K || d / 2 >= K)
        return 0ll;

    auto l = x1;
    auto r = x2;

    if (l > r)
        swap(l, r);

    ++l;
    r -= d / 2 + 1;

    if (l >= K || r < 0 || l > r)
        return 0ll;

    return sum[d / 2][id][min(K - 1, r)] - (l > 0 ? sum[d / 2][id][l - 1] : 0);
}

void solve() {
    for (int d = 1; d < K; ++d) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (s[i][j] == '#') {
                    sum1[d][i + m - 1 - j][i] = (i + d < n && j + d < m && s[i + d][j + d] == '#');
                    sum2[d][i + j][i] = (i + d < n && j - d >= 0 && s[i + d][j - d] == '#');
                }

        for (int id = 0; id < K + K; ++id)
            for (int i = 1; i < K; ++i) {
                sum1[d][id][i] += sum1[d][id][i - 1];
                sum2[d][id][i] += sum2[d][id][i - 1];
            }
    }

    auto ans = 0ll;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (s[i][j] == '#') {
                for (int d = 2; d < K + K; d += 2) {
                    if (i + d < n && s[i + d][j] == '#') {
                        ans += (j >= d / 2 && s[i + d / 2][j - d / 2] == '#');
                        ans += (j + d / 2 < m && s[i + d / 2][j + d / 2] == '#');
                    }

                    if (j + d < m && s[i][j + d] == '#') {
                        ans += (i >= d / 2 && s[i - d / 2][j + d / 2] == '#');
                        ans += (i + d / 2 < n && s[i + d / 2][j + d / 2] == '#');
                    }

                    ans += diag(i - d, j, i, j + d, d, [](int x, int y) { return x + m - 1 - y; }, sum1);
                    ans += diag(i + d, j, i, j - d, d, [](int x, int y) { return x + m - 1 - y; }, sum1);
                    ans += diag(i, j + d, i + d, j, d, [](int x, int y) { return x + y; }, sum2);
                    ans += diag(i, j - d, i - d, j, d, [](int x, int y) { return x + y; }, sum2);
                }
            }

    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (read())
        solve();

    return 0;
}