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>
#define PB push_back
#define LL long long
using namespace std;
string s[300];
int zsuv = 300;
int field[1205][1205];
int prefR[605][605];
int prefH[605][605];
int sumR(int idx , int l , int r)
{
    if(idx < 0)
        return 0;
    if(idx > 600)
        return 0;
    return prefR[idx][r] - (l > 1 ? prefR[idx][l - 2] : 0);
}
int sumH(int idx , int l , int r)
{
    if(idx < 0)
        return 0;
    if(idx > 600)
        return 0;
    return prefH[idx][r] - (l > 1 ? prefH[idx][l - 2] : 0);
}
int main() 
{
    int h , w;
    cin >> h >> w;
    for(int i = 0; i < h; i++)
        cin >> s[i];
    for(int i = 0; i < h; i++)
    {
        for(int j = 0; j < w; j++)
            if(s[i][j] == '#')
            {
                field[i + j][i - j + zsuv] = 1;
            }
    }
    for(int i = 0; i <= 600; i++)
    {
        for(int j = 0; j <= 600; j++)
        {
            prefR[i][j] = field[i][j] + (j > 1 ? prefR[i][j - 2] : 0);
            prefH[j][i] = field[i][j] + (i > 1 ? prefH[j][i - 2] : 0);
        }
    }
    LL ans = 0;
    for(int i = 0; i <= 600; i++)
    {
        for(int j = 0; j <= 600; j++)
        {
            for(int k = j + 2; k <= 600; k += 2)
            {
                if(field[i][j] && field[i][k])
                {
                    //cout << i << " " << j << " " << k << endl;
                    int diff = k - j;
                    
                    ans -= field[i + diff][j + diff];
                    ans -= field[i + diff][j];
                    ans += sumR(i - diff , j , k) + sumR(i + diff , j , k);
                }
                if(field[j][i] && field[k][i])
                {
                    //cout << i << " " << j << " " << k << endl;
                    int diff = k - j;
                    if(i - diff >= 0)
                    ans -= field[k][i - diff];
                    ans -= field[k][i + diff];
                    ans += sumH(i - diff , j , k) + sumH(i + diff , j , k);
                }
            }
        }
    }
    cout << ans;
    return 0;
}