题目描述

译自 ROI 2015 Day1 T3. Вышивка жемчугом

自古以来，在波莫尔地区的村庄中，女手工艺人用珍珠在由相同小格子组成的矩形毛巾上进行刺绣。刺绣从将一颗珍珠缝在某个格子中心开始。为了缝上新的珍珠，手工艺人会从一个已有珍珠的格子沿水平或垂直方向缝一针到相邻的空闲格子，并在针迹末端的格子中心缝上新珍珠。这个过程不断重复，直到珍珠用完为止。

博物馆中保存着一条这样的节日毛巾，可惜的是，部分图案已经丢失，但毛巾的描述记录得以保存。博物馆管理层计划修复毛巾上的一个矩形片段，但尚未决定具体修复哪个片段。修复片段的成本取决于该片段上包含的图案连通部分的数目。图案的一部分被视为连通的，当且仅当其中的任意一颗珍珠可以通过针迹到达该部分内的任意其他珍珠，而不超出该片段的边界。管理层始终将任何两颗可以通过针迹相互到达的珍珠视为属于同一个连通部分。

你的任务是编写一个程序，计算出每个给定片段中的图案连通部分数量。

输入格式

输入数据的第一行包含两个整数 $a$ 和 $b$，分别表示毛巾在水平和垂直方向上的格子数。

第二行包含两个整数 $n$ 和 $q$，分别表示图案中的珍珠数量和片段数量。

接下来的 $(n - 1)$ 行描述针迹。每条针迹属于以下两种类型之一：

• $\texttt{h}\ x\ y$：表示坐标为 $(x, y)$ 和 $(x + 1, y)$ 的格子中含有珍珠，并通过水平针迹连接 $(1 \leq x \leq a - 1, 1 \leq y \leq b)$；
• $\texttt{v}\ x\ y$：表示坐标为 $(x, y)$ 和 $(x, y + 1)$ 的格子中含有珍珠，并通过垂直针迹连接 $(1 \leq x \leq a, 1 \leq y \leq b - 1)$。

由于手工艺人缝制针迹的顺序未知，针迹的描述是任意顺序的。但可以保证图案是按照题目描述的过程生成的。

接下来的 $q$ 行描述片段。每行包含四个整数 $x_1, y_1, x_2, y_2$ $(1 \leq x_1 \leq x_2 \leq a, 1 \leq y_1 \leq y_2 \leq b)$，表示片段左下角和右上角格子的坐标。

输出格式

输出包含 $q$ 行，其中第 $i$ 行包含第 $i$ 个片段中的图案连通部分数量。

4 3
8 4
v 1 1
h 1 1
h 2 1
v 2 1
v 2 2
h 1 3
h 3 1
1 1 4 3
3 2 4 3
3 1 3 1
1 2 3 3

1
0
1
2

下图是对样例的说明。

数据范围与提示

详细子任务附加限制及分值如下表所示：