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 <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using namespace std;


void solve(long long H, long long W, vector<string> s) {
  vector< vector<long long> > d(H+W, vector<long long>(H+W, 0));
  vector< vector<long long> > cx(H+W+1, vector<long long>(H+W, 0));
  vector< vector<long long> > cy(H+W, vector<long long>(H+W+1, 0));
  long long ans = 0;

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (s[i][j] == '#') {
        d[i+j][i-j+W] = 1;
      }
    }
  }

  for (int x = 0; x < H+W; x++) {
    for (int y = 0; y < H+W; y++) {
      cy[x][y+1] = cy[x][y] + d[x][y];
      cx[x+1][y] = cx[x][y] + d[x][y];
    }
  }

  for (int y = 0; y < H+W; y++) {
    for (int x = 0; x < H+W-1; x++) {
      if (d[x][y] != 1) continue;
      for (int xd = 1; x + xd < H+W; xd++) {
        if (d[x+xd][y] == 1) {
          if (y+xd < H+W) {
            ans += cx[x+xd][y+xd] - cx[x][y+xd];
          }
          if (y-xd >= 0) {
            ans += cx[x+xd+1][y-xd] - cx[x+1][y-xd];
          }
        }
      }
    }
  }

  for (int x = 0; x < H+W; x++) {
    for (int y = 0; y < H+W-1; y++) {
      if (d[x][y] != 1) continue;
      for (int yd = 1; y + yd < H+W; yd++) {
        if (d[x][y+yd] == 1) {
          if (x+yd < H+W) {
            ans += cy[x+yd][y+yd+1] - cy[x+yd][y+1];
          }
          if (x-yd >= 0) {
            ans += cy[x-yd][y+yd] - cy[x-yd][y];
          }
        }
      }
    }
  }

  std::cout << ans << std::endl;
}

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

  solve(H, W, s);

  return 0;
}