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>
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <cmath>      // sqrt
#include <cstdlib>    // exit
#include <algorithm>  // min,max
using namespace std;
#define forr(i,m,n) for (int i=(m); i<=(n); i++)
#define forv(i,m,n) for (int i=(m); i>=(n); i--)
#define forall(it,p) for (auto it = p.begin(); it != p.end(); ++it)
#define R 1000000007
#define DBG 1

#define MAXN 602
int b[MAXN][MAXN];
int accz[MAXN][MAXN];
int accu[MAXN][MAXN];

int main() {
  int h,w;
  cin >> h >> w;
  forr(i,0,MAXN-1)
  forr(j,0,MAXN-1)
    b[i][j] = accz[i][j] = accu[i][j] = 0;
  forr(i,0,h-1) {
    string s;
    cin >> s;
    forr(j,0,w-1) {
      b[i-j+w][i+j] = (s[j]=='#' ? 1 : 0);
    }
  }
  forr(z,-w,h-1)
  forr(u,0,w+h-2) {
    accz[z+w][u] = accz[z-1+w][u] + b[z+w][u];
    accu[z+w][u] = accu[z+w][u-1] + b[z+w][u];
  }
  int sum = 0;

  forr(u,0,w+h-1) {
    int lft = (u<w ? -u : u-2*w+2);
    int rgt = (u<h ?  u : 2*h-u-2);
    forr(z,lft,rgt) {
      if (b[z+w][u]==0) continue;
      forr(zz,z+1,rgt) {
        if (b[zz+w][u]==0) continue;
        int uu = u - (zz-z);
        if (uu >= 0) {
          int lft2 = (uu<w ? -uu : uu-2*w+2);
          int rgt2 = (uu<h ?  uu : 2*h-uu-2);
          int z3 = min(zz,rgt2);
          int z4 = max(z,lft2) - 1;
          sum += accz[z3+w][uu] - accz[z4+w][uu];
        }
        uu = u + (zz-z);
        if (uu <= w+h) {
          int lft2 = (uu<w ? -uu : uu-2*w+2);
          int rgt2 = (uu<h ?  uu : 2*h-uu-2);
          int z3 = min(zz,rgt2);
          int z4 = max(z,lft2) - 1;
          sum += accz[z3+w][uu] - accz[z4+w][uu];
        }
      }
    }
  }

    forr(z,-w+1,h-1) {
      int lo = abs(z);
      int hi = (z<h-w ? 2*w+z-2 : 2*h-z-2);
      forr(u,lo,hi) {
        if (b[z+w][u]==0) continue;
        forr(uu,u+2,hi) {
          if (b[z+w][uu]==0) continue;
          int zz = z - (uu-u);
          if (zz >= 1-w) {
            int lo2 = abs(zz);
            int hi2 = (zz<h-w ? 2*w+zz-2 : 2*h-zz-2);
            int u3 = min(uu-1,hi2);
            int u4 = max(u+1,lo2) - 1;
            sum += accu[zz+w][u3] - accu[zz+w][u4];
          }
          zz = z + (uu-u);
          if (zz <= h-1) {
            int lo2 = abs(zz);
            int hi2 = (zz<h-w ? 2*w+zz-2 : 2*h-zz-2);
            int u3 = min(uu-1,hi2);
            int u4 = max(u+1,lo2) - 1;
            sum += accu[zz+w][u3] - accu[zz+w][u4];
          }
        }
      }
    }

    cout << sum << endl;
}