Description

在你去北京的旅行中，你带了很多谜题书，其中很多都包含类似以下的挑战：在图 I.1 中可以找到多少个三角形？

图 I.1：样例输入 2 的插图。

虽然这些谜题让你一时感兴趣，但你很快就对它们感到厌倦，转而开始思考如何用算法来解决它们。谁知道呢，也许这样的题目会在今年的比赛中出现。好吧，猜猜看？今天是你的幸运日！

Input Format

输入的第一行包含两个整数 $r$ 和 $c$ $(1 \le r \le 3000, 1 \le c \le 6000)$，指定图像的大小，其中 $r$ 是顶点的行数，$c$ 是列数。接下来的 $2r - 1$ 行中，每行最多有 $2c - 1$ 个字符。奇数行包含网格顶点（用小写字母 $x$ 表示）和零个或多个水平边，而偶数行包含零个或多个对角边。具体来说，编号为 $4k + 1$ 的行在位置 $1, 5, 9, 13, \ldots$ 处有顶点，而编号为 $4k + 3$ 的行在位置 $3, 7, 11, 15, \ldots$ 处有顶点。输入中表示了所有可能的顶点（例如，参见样例输入 2 中图 I.1 的表示方式）。连接相邻顶点的水平边用三个短划线表示。对角边用一个正斜杠（‘/’）或反斜杠（‘\’）字符表示。边字符将精确地放置在相应顶点之间。所有其他字符将是空格字符。注意，如果任何输入行可能包含尾随空格，则这些空格可能会被省略。

Output Format

显示输入图像中由网格边形成的三角形（任意大小）的数量。

3 3
x---x
 \ /
  x
 / \
x   x

1

4 10
x   x---x---x   x
     \ /   / \
  x   x---x   x   x
     / \ / \   \
x   x---x---x---x
   /   / \   \ / \
  x---x---x---x---x

12

Hint

时间限制：6 秒，内存限制：1024 MB。

题面翻译由 ChatGPT-4o 提供。