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;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H,W; cin >> H >> W;
    vector<string> S(H);
    for (int i=0;i<H;++i) cin >> S[i];
    ll ans0=0,ans1=0;
    for (int _=0;_<2;++_){
        vector<vector<ll>> sum(H+W-1,vector<ll>(H+1,0));
        for (int i=0;i<H;++i)
            for (int j=0;j<W;++j)
                sum[i+j][i+1]+=(S[i][j]=='#');
        for (int i=0;i<H+W-1;++i)
            for (int j=0;j<H;++j)
                sum[i][j+1]+=sum[i][j];
        for (int i=0;i<H;++i){
            for (int j=0;j<W;++j){
                if (S[i][j]!='#') continue;
                for (int k=1;i-k>=0&&j+k<W;++k){
                    if (S[i-k][j+k]!='#') continue;
                    if (i+j+2*k<=H+W-2) ans0+=sum[i+j+2*k][min(H,i+k)]-sum[i+j+2*k][i+1];
                    if (i+j-2*k>=0) ans0+=sum[i+j-2*k][i-k]-sum[i+j-2*k][max(0,i-2*k+1)];
                    ans1+=(i+k<H&&S[i+k][j+k]=='#');
                    ans1+=(j+2*k<W&&S[i][j+2*k]=='#');
                    ans1+=(i-k>=0&&j-k>=0&&S[i-k][j-k]=='#');
                    ans1+=(i-2*k>=0&&S[i-2*k][j]=='#');
                }
            }
        }
        for (int i=0;i<H;++i)
            reverse(S[i].begin(),S[i].end());
    }
    cout << ans0+ans1/2 << '\n';
}