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:
from itertools import accumulate

h, w = map(int, input().split())
field = [input() for _ in range(h)]

l = max(h, w)
precalc_rd = []
precalc_ld = []
for ij in range(h + w - 1):
    coins = [0] * (l + 1)
    min_i = max(0, ij - w + 1)
    max_i = ij - max(0, ij - h + 1)
    offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
    for d in range(max_i - min_i + 1):
        i = min_i + d
        j = ij - i
        if field[i][j] == '#':
            coins[offset + d] = 1
    precalc_ld.append(list(accumulate(coins)))

for ij in range(-w + 1, h):
    coins = [0] * (l + 1)
    min_i = max(0, ij)
    max_i = ij + min(w - 1, h - ij - 1)
    offset = (min_i + (min_i - ij)) // 2 + 1
    for d in range(max_i - min_i + 1):
        i = min_i + d
        j = i - ij
        if field[i][j] == '#':
            coins[offset + d] = 1
    precalc_rd.append(list(accumulate(coins)))

ans = 0

for ij in range(h + w - 1):
    min_i = max(0, ij - w + 1)
    max_i = ij - max(0, ij - h + 1)
    offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
    for sd in range(max_i - min_i + 1):
        si = min_i + sd
        sj = ij - si
        if field[si][sj] == '.':
            continue
        for td in range(sd + 1, max_i - min_i + 1):
            ti = min_i + td
            tj = ij - ti
            if field[ti][tj] == '.':
                continue
            dij = (td - sd) * 2
            if ij - dij >= 0:
                ans += precalc_ld[ij - dij][offset + td - 1] - precalc_ld[ij - dij][offset + sd - 1]
            if ij + dij <= h + w - 2:
                ans += precalc_ld[ij + dij][offset + td] - precalc_ld[ij + dij][offset + sd]

for ij in range(-w + 1, h):
    min_i = max(0, ij)
    max_i = ij + min(w - 1, h - ij - 1)
    offset = (min_i + (min_i - ij)) // 2 + 1
    for sd in range(max_i - min_i + 1):
        si = min_i + sd
        sj = si - ij
        if field[si][sj] == '.':
            continue
        for td in range(sd + 1, max_i - min_i + 1):
            ti = min_i + td
            tj = ti - ij
            if field[ti][tj] == '.':
                continue
            dij = (td - sd) * 2
            if ij - dij + w - 1 >= 0:
                ans += precalc_rd[ij - dij + w - 1][offset + td] - precalc_rd[ij - dij + w - 1][offset + sd]
            if ij + dij + w - 1 <= h + w - 2:
                ans += precalc_rd[ij + dij + w - 1][offset + td - 1] - precalc_rd[ij + dij + w - 1][offset + sd - 1]

print(ans)