题目描述

译自 [CERC2018] Matrice

特工 Sue Thomas 和她的儿子正在网格中寻找 trinity。trinity 是一个新词，正如词素 tri 所示，指的是由网格中单元格组成的三角形。

每个 trinity 是一个正方形的单元格区域去除某对角线上方或下方的部分（一个等腰直角三角形，两腰分别与网格两边分别平行）。对角线可以是主对角线（东南-西北方向），也可以是副对角线（西南-东北方向）。一个合法的 trinity 至少包含三个单元格，并且所有单元格中字符都相同。

输入格式

输入的第一行是两个整数 $N,M$，分别表示这个网格的行数和列数。

接下来 $N$ 行每行一个长为 $M$ 的字符串，表示这个网格。

输出格式

输出网格中所有不同合法的 trinity 个数。

2 2
AA
Ad

1

5 5
#####
####.
###..
##...
#....

60

5 4
hwwr
eahe
lroy
lswo
oaau

0

5 6
#girls
##areb
#.#est
#..#!!
#####!

7

提示

$1≤N,m≤10^3$，保证输入中出现的字符 ASCII 码在 $33$ 到 $126$ 之间。