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 long LL;

char s[500][500];
int pre1[3000][3000] = {0}, pre2[3000][3000] = {0};
const int shift = 1000;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, m; cin >> n >> m;
  auto inside = [](int x, int n) { return x >= 0 and x < n; };
  for (int i = 0; i < n; ++i) cin >> s[i];
  for (int i = 0; i + 1 < 3000; ++i) for (int j = 0; j + 1 < 3000; ++j) {
    pre1[i + 1][j + 1] = pre1[i][j] + 
    (inside(i - shift, n) and inside(j - shift, m) ? 
    s[i - shift][j - shift] == '#' : 0);
  }
  for (int i = 0; i + 1 < 3000; ++i) for (int j = 1; j < 3000; ++j) {
    pre2[i + 1][j - 1] = pre2[i][j] + 
    (inside(i - shift, n) and inside(j - shift, m) ?
    s[i - shift][j - shift] == '#' : 0);
  }
  LL diag = 0;
  auto S = [&](int i, int j) {
    i -= shift, j -= shift;
    if (inside(i, n) and inside(j, m)) return int(s[i][j] == '#');
    else return 0;
  };
  auto go1 = [&](int i, int j, int d) {
    i += shift, j += shift;
    diag += S(i, j + 2 * d) + S(i - d, j + d) + S(i + 2 * d, j) + S(i + d, j - d);
    return pre1[i + 1][j + 2 * d + 1] - pre1[i - d][j + d] +
           pre1[i + 2 * d + 1][j + 1] - pre1[i + d][j - d];
  };
  auto go2 = [&](int i, int j, int d) {
    i += shift, j += shift;
    diag += S(i + 2 * d, j) + S(i + d, j + d) + S(i, j - 2 * d) + S(i - d, j - d);
    return pre2[i + 2 * d + 1][j - 1] - pre2[i + d][j + d] + 
           pre2[i + 1][j - 2 * d - 1] - pre2[i - d][j - d]; 
  };
  LL ans = 0;
  for (int d = 1; d < 700; ++d) {
    for (int i = 0; i + d < n; ++i) {
      for (int j = 0; j + d < m; ++j) {
        if (s[i][j] == '#' and s[i + d][j + d] == '#') {
          ans += go1(i, j, d);
        }
      }
    }
  }
  for (int d = 1; d < 700; ++d) {
    for (int i = 0; i + d < n; ++i) {
      for (int j = m - 1; j - d >= 0; --j) {
        if (s[i][j] == '#' and s[i + d][j - d] == '#') {
          ans += go2(i, j, d);
        }
      }
    }
  }
  cout << ans - diag / 2 << '\n';
}