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;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int n, m;
int ma[610][610];
int ps[610][610];

int sum(int a, int b, int c, int d) {
    return ps[c][d]-ps[a-1][d]-ps[c][b-1]+ps[a-1][b-1];
}

char buf[310];
int main() {
    int i, j, k;

    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) {
        scanf("%s",buf);
        for (j=1;j<=m;j++) ma[i+j-1][i-j+m] = (buf[j-1]=='#');
    }
    for (i=1;i<n+m;i++) {
        for (j=1;j<n+m;j++) {
            ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+ma[i][j];
        }
    }
    ll su = 0;
    for (i=1;i<n+m;i++) {
        for (j=1;j<n+m;j++) {
            if (!ma[i][j]) continue;
            for (k=1;k<n+m;k++) {
                if (k==j) continue;
                if (!ma[i][k]) continue;
                if (abs(k-j)<i)su += sum(i-abs(k-j),min(j,k),i-abs(k-j),max(j,k))-ma[i-abs(k-j)][j];
                if (abs(k-j)+i<n+m)su += sum(i+abs(k-j),min(j,k),i+abs(k-j),max(j,k))-ma[i+abs(k-j)][j];
            }
            for (k=1;k<n+m;k++) {
                if (k==i) continue;
                if (!ma[k][j]) continue;
                if (abs(k-i)<j)su += sum(min(i,k),j-abs(k-i),max(i,k),j-abs(k-i))-ma[i][j-abs(k-i)];
                if (abs(k-i)+j<n+m)su += sum(min(i,k),j+abs(k-i),max(i,k),j+abs(k-i))-ma[i][j+abs(k-i)];
            }
        }
    }
    printf("%lld\n",su/2);

    return 0;
}