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<bitset>
using namespace std;
int h,w;
string s[300];
bitset<300>f[300];
long ans,now;
int main()
{
	cin>>h>>w;
	for(int i=0;i<h;i++)
	{
		cin>>s[i];
		for(int j=0;j<w;j++)f[i][j]=s[i][j]=='#';
	}
	for(int x=1;x<h;x++)for(int y=1;y<w;y++)
	{
		if((x*2+y*2)%3)continue;
		int cnt=(x*2+y*2)/3;
		if(cnt<x||cnt<y)continue;
		now=0;
		if(x==y*2)
		{
			for(int i=0;i<h-x;i++)now+=(f[i]&f[i+x]&f[i+x/2]>>y).count();
			//for(int j=0;j<w-y;j++)now+=f[i][j]&&f[i+x][j]&&f[i+x/2][j+y];
			for(int i=0;i<h-x;i++)now+=(f[i]&f[i+x]&f[i+x/2]<<y).count();
			//for(int j=y;j<w;j++)now+=f[i][j]&&f[i+x][j]&&f[i+x/2][j-y];
		}
		else if(y==x*2)
		{
			for(int i=0;i<h-x;i++)now+=(f[i]&f[i]>>y&f[i+x]>>y/2).count();
			//for(int j=0;j<w-y;j++)now+=f[i][j]&&f[i][j+y]&&f[i+x][j+y/2];
			for(int i=x;i<h;i++)now+=(f[i]&f[i]>>y&f[i-x]>>y/2).count();
			//for(int j=0;j<w-y;j++)now+=f[i][j]&&f[i][j+y]&&f[i-x][j+y/2];
		}
		else
		{
			for(int i=0;i<h-x;i++)now+=(f[i]&f[i+x]>>cnt-x&f[i+cnt-y]>>y).count();
			//for(int j=0;j<w-y;j++)now+=f[i][j]&&f[i+x][j+cnt-x]&&f[i+cnt-y][j+y];
			for(int i=0;i<h-x;i++)now+=(f[i]&f[i+x]<<cnt-x&f[i+cnt-y]<<y).count();
			//for(int j=y;j<w;j++)now+=f[i][j]&&f[i+x][j-cnt+x]&&f[i+cnt-y][j-y];
			for(int i=x;i<h;i++)now+=(f[i]&f[i-x]>>cnt-x&f[i-cnt+y]>>y).count();
			//for(int j=0;j<w-y;j++)now+=f[i][j]&&f[i-x][j+cnt-x]&&f[i-cnt+y][j+y];
			for(int i=x;i<h;i++)now+=(f[i]&f[i-x]<<cnt-x&f[i-cnt+y]<<y).count();
			//for(int j=y;j<w;j++)now+=f[i][j]&&f[i-x][j-cnt+x]&&f[i-cnt+y][j-y];
		}
		ans+=now;
	}
	cout<<ans<<endl;
}