题目描述

儿童棋盘游戏由一个方形的点数组组成,其中包含连接一些点的线条。游戏的一部分要求玩家计算这些线形成的正方形数。例如,在下图中,有3个平方,2个大小为1,大小为2,因此平方总数为3。(正方形的“大小”是形成侧面所需的线段数。

你的任务是写一个程序来计算所有可能的正方形的数量。

输入

输入代表一系列游戏板。每个板由一个平方数组的$n ^ 2$个点$(其中2 <= n <= 1500)$和一些相互连接的水平和垂直线组成。具有$n ^ 2$个点和$m(m <=30000)$互连行的单个板的记录如下:

第1行:$“n”$单行或列中的点数。

第2行:$“m”$互连线路数。

下一个 $m$行是以下两种类型之一:

$“H i j k”(1 <= i,j <= n,k >0,j + k <= n)$表示从行$i$中的点的水平长度k,列j到行i中的点,列j到行i中的点,列$j$。

或

$“V i j k”(1 <= i,j <= n,k >0,i + k <= n)$表示长度$k$的垂直行,从行$i$,列$j$到行$i + k$,列$j$到行中的点。

输入的结束用文件结尾表示。

输出：

对于每个记录,打印只有一个整数,即平方数。 输入数 1

4
9
H 1 1 1
H 1 3 1
H 2 1 3
H 3 2 1
H 4 2 2
V 1 1 1
V 1 2 3
V 2 3 1
V 1 4 3
4
9
H 1 1 1
H 1 3 1
H 2 1 3
H 3 2 1
H 4 2 2
V 1 1 1
V 1 2 3
V 2 3 1
V 1 4 3

输出数位 1

3
3

来源

POJ 月刊, 张林