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

Solution:
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        int[][] a = new int[h+w+1][h+w+1];
        
        for(int i=0; i<h; i++){
            String line = sc.next();
            for(int j=0; j<w; j++){
                if(line.charAt(j)=='#'){
                    a[1+i+j][w+i-j] = 1;
                }
            }
        }
        
        int[][] hs = new int[h+w+1][h+w+1];
        int[][] vs = new int[h+w+1][h+w+1];
        
        for(int i=1; i<=h+w; i++){
            for(int j=1; j<h+w; j++){
                hs[i][j] += a[i][j] + hs[i][j-1];
                vs[i][j] += a[i][j] + vs[i-1][j];
            }
        }
        
        long cnt = 0;
        for(int i=0; i<h+w; i++){
            for(int j=0; j<h+w; j++){
                for(int k=j+1; k<h+w; k++){
                    int d = k-j;
                    if(a[i][j]==1 && a[i][k]==1){
                        if(0 <= i-d){
                            cnt += hs[i-d][k] - hs[i-d][j-1];
                            cnt -= a[i-d][j] + a[i-d][k];
                        }
                        if(i+d <= h+w){
                            cnt += hs[i+d][k] - hs[i+d][j-1];
                            cnt -= a[i+d][j] + a[i+d][k];
                        }
                    }
                    if(a[j][i]==1 && a[k][i]==1){
                        if(0 <= i-d){
                            cnt += vs[k][i-d] - vs[j-1][i-d];
                        }
                        if(i+d <= h+w){
                            cnt += vs[k][i+d] - vs[j-1][i+d];
                        }
                    }
                }
            }
        }
        
        System.out.println(cnt);
    }
}