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 <stdio.h>
#include <stdlib.h>

using namespace std;
char Map[1005][1005]={0};
int con1[1005][1005]={0};
int con2[1005][1005]={0};
int main()
{
    int N,M,ans=0,i,j,k,x1,y1,x2,y2;
    scanf("%d %d\n",&N,&M);
    for(i=301;i<N+301;i++)
    {
        fgets(Map[i]+301,1000,stdin);
    }
    for(i=0;i<=1000;i++)
    {
    	for(j=0;j<=1000;j++)
    	{
    	    //printf("%c",Map[i][j]);
    		con1[i][j]=(Map[i][j]=='#');
    		con2[i][j]=(Map[i][j]=='#');
    		if(i) con1[i][j]+=con1[i-1][j-1];
    		if(i) con2[i][j]+=con2[i-1][j+1];
		}

	}


    for(i=301;i-301<N;i++)
    {
    	for(j=301;j-301<M;j++)
    	{
    	    //printf("%d %d %c\n",i,j,Map[i][j]);
    		if(Map[i][j]=='.') continue;
    		for(k=1;k<max(N,M);k++)
    		{
    		    if(Map[i+k][j-k]=='#')
                {
                    ans+=con2[i+2*k][j]-con2[i+k][j+k]+(Map[i+k][j+k]=='#');
                    //printf("a %d %d\n",k,ans);
                    ans+=con2[i][j-2*k]-con2[i-k][j-k]+(Map[i-k][j-k]=='#');
                    //printf("a %d %d\n",k,ans);

                }

			}

			for(k=2;k<max(N,M);k++)
    		{
    		    if(Map[i+k][j+k]=='#')
                {

                    ans+=con1[i-1][j+2*k-1]-con1[i-k+1][j+k+1]+(Map[i-k+1][j+k+1]=='#');
                    ans+=con1[i+2*k-1][j-1]-con1[i+k+1][j-k+1]+(Map[i+k+1][j-k+1]=='#');
                    //printf("b %d %d\n",k,ans);
                }
			}
            //printf("%d %d %d %c\n",i,j,ans,Map[i][j]);


		}
	}
 	printf("%d\n",ans);
    return 0;
}