CF1181C Flag

Innokenty 在跳蚤市场工作，出售一些稀有物品。最近他发现了一条旧的矩形毯子。结果发现，这条毯子被分成了 $n \times m$ 个有颜色的格子，形成了一个有 $n$ 行 $m$ 列的矩形。 这些彩色的格子引起了 Innokenty 的注意，于是他立刻想出了如下的商业计划：如果他从毯子上裁剪出一个由三条彩色条纹组成的子矩形，他就可以把它当作某个国家的国旗来出售。Innokenty 认为，如果一个子矩形由三条等高、上下排列的条纹组成，并且每条条纹的所有格子颜色相同，那么它就足够像某个国家的国旗。当然，最上面那条条纹的颜色必须与中间那条不同，中间那条的颜色也必须与最下面那条不同。 Innokenty 还没有决定要裁剪哪一部分，但他确定国旗的边界必须沿着网格线，并且不会旋转毯子。请帮助 Innokenty 统计他可以裁剪并出售的不同子矩形的数量。即使两个子矩形形成的国旗完全相同，只要它们的位置不同，也被视为不同的子矩形。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$），表示毯子的行数和列数。 接下来的 $n$ 行，每行包含 $m$ 个小写英文字母（'a' 到 'z'），描述了毯子的每一行。相同的字母表示相同的颜色，不同的字母表示不同的颜色。

输出一行，表示可以形成合法国旗的子矩形的数量。

下图中选中的子矩形在第一个样例中是合法的国旗。   由 ChatGPT 4.1 翻译