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;
int a[2009][2009];
int c1[2009][2009];
int c2[2009][2009];
int cn1(int s, int x1, int x2){
    return c1[x2 + 600][s - x2 + 600] - c1[x1 - 1 + 600][s - x1 + 1 + 600];
}
int cn2(int s, int x1, int x2){
    return c2[x2 + 600][-s + x2 + 600] - c2[x1 - 1 + 600][-s + x1 - 1 + 600];
}
int f(int x, int y){
    if (x>=0 && y >=0 && a[x][y]) return 1;
    return 0;
}
int main(){
   int H, W;
   cin >> H >> W;
   for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            char c;
            cin >> c;
            if(c == '#') a[i][j] = 1;
        }
   }
   for(int i = -W-1; i <= H + H + W+1; i++){
        for(int j = - H-1; j <= H + W + W+1; j++){

            c1[i + 600][j+ 600] =  c1[i - 1+ 600][j + 1+ 600];
            c2[i+ 600][j+ 600] =  c2[i - 1+ 600][j - 1+ 600];
            if(i >=0 && j>=0 && a[i][j]) c1[i + 600][j + 600] ++,
                                  c2[i + 600][j + 600] ++;
        }
   }
   int ans = 0;
   for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            for(int d = 1; d <= H + W ; d++){
                int c1 = f(i, j + d);
                int c2 = f(i + d, j);
                int c3 = f(i, j - d);
                int c4 = f(i - d, j);
                int s3 = cn1(i + j + d, i, i + d);
                int s4 = cn2(i + d - j, i, i + d);
                int s1 = cn1(i + j - d, i - d, i);
                int s2 = cn2(i - j - d, i - d, i);
                if(c1 && c2) ans += s1;
                if(c2 && c3) ans += s2;
                if(c3 && c4) ans += s3;
                if(c4 && c1) ans += s4;
                if(c1 + c2 + c3 +c4 == 4) ans -= 4;
                if(c1 + c2 + c3 +c4 == 3) ans --;
            }
        }
   }
   cout<< ans <<endl;
}