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;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
//const int mod = ;

vvi rot(vvi a) {
  int n = a.size(), m = a[0].size();
  vvi b(m, vi(n));
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
    b[j][n-1-i] = a[i][j];
  }
  return b;
}

ll f(const vvi& a) {
  int n = a.size(), m = a[0].size();
  int res = 0;
  for (int i = 0; i < n; ++i) {
    for (int l = 0; l < m; ++l) if (a[i][l]) {
      for (int r = l + 2; r < m; r += 2) if (a[i][r]) {
        int x = (l + r) / 2;
        int d = (r - l) / 2;
        if (i >= d && a[i-d][x]) ++res;
        if (i + d < n && a[i+d][x]) ++res;
      }
    }
  }
  cerr << "f: " << res << endl;
  return res;
}

ll g(const vvi& a) {
  int n = a.size(), m = a[0].size();
  ll res = 0;
  vvi s(n + 1, vi(m + 1));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      s[i + 1][j + 1] = s[i][j] + a[i][j];
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int l = 0; l < m; ++l) if (a[i][l]) {
      for (int d = 1; d < min(n - i, m - l); ++d) if (a[i + d][l + d]) {
        int i1 = i - d, j1 = l + d;
        int i2 = i, j2 = l + 2 * d;
//        cerr << i << ' ' << l << ' ' << d << ' ' << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << endl;
        if (i1 < 0) {
          j1 -= i1;
          i1 = 0;
        }
        if (j2 >= m) {
          i2 -= j2 - m + 1;
          j2 = m - 1;
        }
        if (i1 <= i2) {
          res += s[i2+1][j2+1] - s[i1][j1];
//          cerr << i << ' ' << l << ' ' << d << ' ' << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << endl;
        }
        i1 = i + d, j1 = l - d;
        i2 = i + 2 * d, j2 = l;
        if (j1 < 0) {
          i1 -= j1;
          j1 = 0;
        }
        if (i2 >= n) {
          j2 -= i2 - n + 1;
          i2 = n - 1;
        }
        if (i1 <= i2) {
          res += s[i2+1][j2+1] - s[i1][j1];
        }
      }
    }
  }
  cerr << "g: " << res << endl;
  return res;
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  int n, m;
  cin >> n >> m;
  vs s(n);
  vvi a(n, vi(m));
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
    for (int j = 0; j < m; ++j) {
      a[i][j] = s[i][j] == '#';
    }
  }
  ll res = g(a) - f(a);
  auto b = rot(a);
  res += g(b) - f(b);
  cout << res << endl;
  return 0;
}