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 PYTHON3):

Solution:
# E
H, W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(list(input()))

res = 0
# cross
cross_posi = [[0]*(H+W-1) for _ in range(H+W-1)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            cross_posi[i+j][i-j+W-1] = 1
            
# pre-compute
cross_posi_1 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[i][j]
        cross_posi_1[i][j+1] = r
        
cross_posi_2 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[j][i]
        cross_posi_2[i][j+1] = r

for s in range(H+W-1):
    for t in range((s+W+1)%2, H+W-2, 2):
        if cross_posi[s][t] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[s][u] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_1[s-d][u+1] - cross_posi_1[s-d][t]
                    if s+d < H+W-1:
                        res += cross_posi_1[s+d][u+1] - cross_posi_1[s+d][t]
for s in range(H+W-1):
    for t in range((s+W+1)%2, H+W-2, 2):
        if cross_posi[t][s] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[u][s] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_2[s-d][u] - cross_posi_2[s-d][t+1]
                    if s+d < H+W-1:
                        res += cross_posi_2[s+d][u] - cross_posi_2[s+d][t+1]
print(res)