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:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
tenka1-2018 E
"""

from itertools import product
from itertools import combinations

h, w = map(int, input().split())
slili = [list(input()) for i in range(h)]

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '#':
        coinsetli[i+j+1].add(j-i)

jmin = -304
jmin2 = jmin+2


coinacumdictli = [[] for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(jmin+tt, 303, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i].append(tmp)


coinacumdictli2 = [[] for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(len(coinacumdictli[i])-1):
        coinacumdictli2[i].append(coinacumdictli[i][j]+coinacumdictli[i][j+1])


coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
    tt = (i % 2) - 1

    def rescale(x):
        return (x-jmin2-tt)//2
    coinlili[i] = sorted(list(map(rescale, coinsetli[i])))


ansdouble = 0
for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinlili[i], 2):
        j = 2*(y-x)
        imj = i-j
        ipj = i+j
        if imj >= 1:
            ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
        if ipj <= h+w-1:
            ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]

# repeat after reversing along the vertical axis
for i in range(h):
    slili[i].reverse()

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '#':
        coinsetli[i+j+1].add(j-i)

jmin = -304
jmin2 = jmin+2

coinacumdictli = [[] for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(jmin+tt, 303, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i].append(tmp)


coinacumdictli2 = [[] for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(len(coinacumdictli[i])-1):
        coinacumdictli2[i].append(coinacumdictli[i][j]+coinacumdictli[i][j+1])

coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
    tt = (i % 2) - 1

    def rescale(x):
        return (x-jmin2-tt)//2
    coinlili[i] = sorted(list(map(rescale, coinsetli[i])))


for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinlili[i], 2):
        j = 2*(y-x)
        imj = i-j
        ipj = i+j
        if imj >= 1:
            ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
        if ipj <= h+w-1:
            ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]

print(ansdouble//2)