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;

using int64 = long long;

vector< string > rot(vector< string > &s) {
  vector< string > t(s[0].size(), string(s.size(), '*'));
  for(int i = 0; i < s.size(); i++) {
    for(int j = 0; j < s[i].size(); j++) {
      t[j][i] = s[i][s[i].size() - j - 1];
    }
  }
  return t;
}

int main() {
  int H, W;
  cin >> H >> W;
  vector< string > S(H);
  for(int i = 0; i < H; i++) {
    cin >> S[i];
  }

  int64 ret = 0;
  for(int i = 0; i < 4; i++) {
    S = rot(S);
    vector< int > st[600];
    for(int j = 0; j < S.size(); j++) {
      for(int k = 0; k < S[j].size(); k++) {
        if(S[j][k] == '#') st[j + k].emplace_back(j - k);
      }
    }
    for(int j = 0; j < 600; j++) {
      sort(begin(st[j]), end(st[j]));
    }
    for(int j = 0; j < 600; j++) {
      for(int k = 0; k < st[j].size(); k++) {
        for(int l = k + 1; l < st[j].size(); l++) {
          auto d = st[j][l] - st[j][k];
          if(j + d >= 600) continue;
          auto &it = st[j + d];
          ret += lower_bound(begin(it), end(it), st[j][l]) - lower_bound(begin(it), end(it), st[j][k]);
        }
      }
    }
  }
  cout << ret << endl;
}