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>
#define REP(i, a, n) for (ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

int main(void) {
  ll H, W;
  cin >> H >> W;
  vector<string> S(H);
  REP(i, 0, H) cin >> S[i];

  vector<vector<ll>> s1(H + W - 1, vector<ll>(W + 1));
  REP(i, 0, H + W - 1) {
    for (ll y = H - i - 1, x = 0; x < W; y++, x++) {
      if (0 <= y && y < H && S[y][x] == '#') {
        s1[i][x + 1]++;
      }
    }
    REP(j, 0, W) s1[i][j + 1] += s1[i][j];
  }
  vector<vector<ll>> s2(H + W - 1, vector<ll>(W + 1));
  REP(i, 0, H + W - 1) {
    for (ll y = i, x = 0; x < W; y--, x++) {
      if (0 <= y && y < H && S[y][x] == '#') {
        s2[i][x + 1]++;
      }
    }
    REP(j, 0, W) s2[i][j + 1] += s2[i][j];
  }

  ll ans = 0, ans2 = 0;
  REP(i, 0, H) REP(j, 0, W) if (S[i][j] == '#') {
    for (ll y = i + 1, x = j + 1; y < H && x < W; y++, x++) if (S[y][x] == '#') {
      ll t = y - i;
      {
        ll u = H - (i - j + t * 2) - 1, l = max(j - t, 0LL), r = min(j + 1, W);
        if (0 <= u && u < H + W - 1 && l < r) {
          ans += s1[u][r] - s1[u][l];
          if (j - t >= 0 && s1[u][j - t + 1] - s1[u][j - t] > 0) ans2++;
          if (j < W && s1[u][j + 1] - s1[u][j] > 0) ans2++;
        }
      }
      {
        ll u = H - (i - j - t * 2) - 1, l = max(j + t, 0LL), r = min(j + t * 2 + 1, W);
        if (0 <= u && u < H + W - 1 && l < r) {
          ans += s1[u][r] - s1[u][l];
          if (j + t >= 0 && s1[u][j + t + 1] - s1[u][j + t] > 0) ans2++;
          if (j + t * 2 < W && s1[u][j + t * 2 + 1] - s1[u][j + t * 2] > 0) ans2++;
        }
      }
    }
    for (ll y = i + 1, x = j - 1; y < H && x >= 0; y++, x--) if (S[y][x] == '#') {
      ll t = y - i;
      {
        ll u = i + j - t * 2, l = max(j - t * 2, 0LL), r = min(j - t + 1, W);
        if (0 <= u && u < H + W - 1 && l < r) {
          ans += s2[u][r] - s2[u][l];
          if (j - t * 2 >= 0 && s2[u][j - t * 2 + 1] - s2[u][j - t * 2]) ans2++;
          if (j - t < W && s2[u][j - t + 1] - s2[u][j - t] > 0) ans2++;
        }
      }
      {
        ll u = i + j + t * 2, l = max(j, 0LL), r = min(j + t + 1, W);
        if (0 <= u && u < H + W - 1 && l < r) {
          ans += s2[u][r] - s2[u][l];
          if (j >= 0 && s2[u][j + 1] - s2[u][j] > 0) ans2++;
          if (j + t < W && s2[u][j + t + 1] - s2[u][j + t] > 0) ans2++;
        }
      }
    }
  }
  cout << ans - ans2 / 2 << endl;
}