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;

long long h, w;
vector<string> s;

long long solve();

int main() {
  cin >> h >> w;
  s.resize(h);
  for (auto& p : s) cin >> p;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0;
  auto calc = [](bool ch) {
    long long res = 0;
    vector<vector<int>> sum(h, vector<int>(w, 0));
    using P = pair<int, int>;
    vector<vector<P>> points(h + w);
    for (int i = 0; i < h; ++i)
      for (int j = 0; j < w; ++j) {
        if (i && j) sum[i][j] += sum[i - 1][j - 1];
        if (s[i][j] == '#') {
          ++sum[i][j];
          points[i - j + w].emplace_back(i, j);
        }
      }
    for (auto v : points) {
      int len = v.size();
      for (int i = 0; i < len; ++i)
        for (int j = i + 1; j < len; ++j) {
          P a = v[i], b = v[j];
          int dif = b.first - a.first;
          assert(dif == b.second - a.second);
          auto calcsec = [&](P c, P d) {
            long long res = 0;
            int now = max({0LL, d.first - (h - 1), d.second - (w - 1)});
            d.first -= now, d.second -= now;
            if (d.first < 0 || d.second < 0 || c.first >= h || c.second >= w)
              return 0LL;
            res += sum[d.first][d.second];
            if (c.first >= 0 && c.second >= 0) res -= sum[c.first][c.second];
            return res;
          };
          // down
          P d(a.first + 2 * dif - ch, a.second - ch),
              c(b.first - 1 + ch, b.second - 2 * dif - 1 + ch);
          res += calcsec(c, d);
          // up
          d = P(a.first - ch, a.second + 2 * dif - ch);
          c = P(b.first - 2 * dif - 1 + ch, b.second - 1 + ch);
          res += calcsec(c, d);
        }
    }
    return res;
  };
  res += calc(0);
  for (int i = 0; i < h; ++i) reverse(s[i].begin(), s[i].end());
  res += calc(1);
  return res;
}