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 <iostream>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <fstream>
#include <bitset>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <iomanip>
#include <stdio.h>
#include <string.h>
#include <random>
#include <functional>
using namespace std;
#define all(x) (x).begin(), (x).end()
 
const int N = 500000;
const long long MOD = 1e9 + 7;
 
int n, m;
vector<string> s;
long long ans = 0;
 
void R()
{
    vector<string> f(m, string(n, ' '));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            f[m - 1 - j][i] = s[i][j];
        }
    }
    swap(n, m);
    s = f;
    return;
}
 
void F()
{
    vector<vector<int> > summ(n, vector<int>(m));
    function<int(int, int)>G = [&](int i, int j)
    {
        if (j < 0 || j + i < 0 || i >= n) return 0;
        if (i < 0)
        {
            j -= -i;
            i += -i;
        }
        return summ[i][j];
    };
    function<int(int, int)>M = [&](int i, int j)
    {
        if (i < 0 || j < 0 || i >= n || j >= m) return 0;
        return (int)(s[i][j] == '#');
    };
    for (int si = 0; si < n + m - 1; si++)
    {
        for (int i = si; i >= 0; i--)
        {
            int j = si - i;
            if (0 <= i && i < n && 0 <= j && j < m)
            {
                summ[i][j] = G(i + 1, j - 1) + M(i, j);
            }
        }
    }
    for (int s = 0; s < n + m - 1; s++)
    {
        for (int i1 = 0; i1 <= s; i1++)
        {
            for (int i2 = 0; i2 <= s; i2++)
            {
                int j1 = s - i1, j2 = s - i2;
                if (j1 < j2 && 0 <= j1 && j1 < m && 0 <= j2 && j2 < m && M(i1, j1) && M(i2, j2))
                {
                    int k = j2 - j1;
                    int i3 = i2, j3 = j1 - k;
                    int i4 = i2 - k, j4 = j1;
                    i3++, j3--;
                    ans += G(i4, j4) - G(i3, j3);
                }
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int k = 1; k <= 300; k++)
            {
                if (M(i + k, j) && M(i, j + k) && M(i - k, j)) ans--;
            }
        }
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    s.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    F();
    R();
    F();
    R();
    F();
    R();
    F();
    cout << ans;
}