Contest Duration: - (local time) (100 minutes) Back to Home
E - Equilateral /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

xy 平面上にコインがいくつかあります。 コインの配置は HW 列のグリッドを用いて表され、グリッドの ij 列目の文字 s_{ij}# のとき座標 (i,j) にコインがひとつあることを、 . のとき座標 (i,j) にコインがないことを表します。 その他に xy 平面上にコインは存在しません。

• 3 つのうちどの 2 つのコインをとっても、それらの存在する座標の間のマンハッタン距離が一定である

ただし、座標 (x,y),(x',y') の間のマンハッタン距離は、|x-x'|+|y-y'| で表されます。 また、コインの順番を入れ替えただけの組は同じものとみなします。

### 制約

• 1 \leq H,W \leq 300
• s_{ij}# または . である

### 入力

H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}


### 入力例 1

5 4
#.##
.##.
#...
..##
...#


### 出力例 1

3


((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)),((1,3),(3,1),(4,4)) が条件を満たします。

### 入力例 2

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####


### 出力例 2

870


Score : 700 points

### Problem Statement

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.

### Sample Input 1

5 4
#.##
.##.
#...
..##
...#


### Sample Output 1

3


((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)) and ((1,3),(3,1),(4,4)) satisfy the condition.

### Sample Input 2

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####


### Sample Output 2

870