在前往北京的旅途中,你带了许多益智书,其中许多书里都有类似这样的挑战:图 I.1 中有多少个三角形?
图 I.1:样例输入 2 的示意图。
虽然这些谜题能让你暂时感兴趣,但你很快就会对它们感到厌倦,转而开始思考如何用算法来解决它们。谁知道呢,也许这样的问题真的会出现在今年的比赛中。好吧,你猜怎么着?今天就是你的幸运日!
输入格式
输入的第一行包含两个整数 $r$ 和 $c$ ($1 \le r \le 3\,000, 1 \le c \le 6\,000$),指定了图片的大小,其中 $r$ 是顶点的行数,$c$ 是列数。接下来有 $2r - 1$ 行,每行最多包含 $2c - 1$ 个字符。奇数行包含网格顶点(用小写字母 x 表示)和零个或多个水平边,而偶数行包含零个或多个对角边。具体来说,编号为 $4k + 1$ 的行在位置 $1, 5, 9, 13, \dots$ 处有顶点,而编号为 $4k + 3$ 的行在位置 $3, 7, 11, 15, \dots$ 处有顶点。输入中表示了所有可能的顶点(例如,参见样例输入 2 中图 I.1 的表示方式)。连接相邻顶点的水平边用三个短横线表示。对角边用单个正斜杠('/')或反斜杠('\')字符表示。边字符将精确放置在对应顶点之间。所有其他字符均为空格。注意,如果任何输入行包含尾随空格,则这些空格可能会被省略。
输出格式
显示输入图片中由网格边形成的三角形(任意大小)的数量。
样例
样例输入 1
3 3 x---x \ / x / \ x x
样例输出 1
1
样例输入 2
4 10 x x---x---x x \ / / \ x x---x x x / \ / \ \ x x---x---x---x / / \ \ / \ x---x---x---x---x
样例输出 2
12