P14264 [ROI 2015 Day1] 珍珠刺绣

**译自 [ROI 2015](https://neerc.ifmo.ru/school/archive/2014-2015.html) Day1 T3.** ***[Вышивка жемчугом](https://neerc.ifmo.ru/school/archive/2014-2015/ru-olymp-roi-2015-day1.pdf)***

自古以来，北方沿海村庄的手工艺人们便在由方格组成的长方形布巾上用珍珠进行刺绣装饰。刺绣的开始是将第一颗珍珠缝在某个方格的中心位置。为了缝上下一颗珍珠，手工艺人会从**已经有珍珠的方格**向**在水平方向或垂直方向相邻的空方格**做一针，然后将新的珍珠缝在这针末端方格的中心。这一过程不断重复，直到所有珍珠都缝制完成。 其中一块节日用的珍珠刺绣布如今保存在博物馆中。不幸的是，部分刺绣图案已经遗失，但布巾的结构信息仍被保存下来。博物馆计划修复布巾上的某一个**矩形区域**，但尚未决定具体修复哪一块。修复某个区域的成本与该区域中**连通的图案部分**的数量有关。 我们称一部分图案是**连通的**，如果在不离开该区域的前提下，可以沿着针脚从其中任意一颗珍珠移动到另一颗珍珠。博物馆总是将可以通过针脚互相到达的所有珍珠视为属于同一个连通部分。 你的任务是编写一个程序，对于给定的每个矩形区域，计算其中**连通部分的数量**。

第一行包含两个整数 $a$ 和 $b$ —— 布巾在水平方向和垂直方向上的方格数。 第二行包含两个整数 $n$ 和 $q$ —— 图案中珍珠的总数，以及需要查询的区域数。 接下来的 $(n - 1)$ 行描述针脚的连接情况。每一行表示一根针脚，格式如下： - `h` $x$ $y$：表示方格 $(x, y)$ 和 $(x + 1, y)$ 各有一颗珍珠，它们通过一根**水平针脚**连接（$1 \le x \le a - 1$；$1 \le y \le b$）。 - `v` $x$ $y$：表示方格 $(x, y)$ 和 $(x, y + 1)$ 各有一颗珍珠，它们通过一根**垂直针脚**连接（$1 \le x \le a$；$1 \le y \le b - 1$）。 针脚的顺序是任意的，因为我们不知道手工艺人在缝制时的具体顺序。可以保证，这些针脚描述的图案可以通过题目开头所述的缝制过程得到。 接下来的 $q$ 行描述需要查询的矩形区域。每行包含四个整数 $x_1$, $y_1$, $x_2$, $y_2$ —— 分别表示矩形区域左下角和右上角方格的坐标（$1 \le x_1 \le x_2 \le a$；$1 \le y_1 \le y_2 \le b$）。

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个矩形区域内的**连通部分数量**。

### 样例解释 下图给出了题目描述中测试用例的示意图，展示了针脚连接形成的珍珠图案结构。 :::align{center}  ::: ### 数据范围 | 子任务编号 | 分值 | $a, b$ 范围 | $n$ 范围 | $q$ 范围 | |:--:|:--:|:--:|:--:|:--:| | 1 | 28 | $1 \le a, b \le 100$ | $2 \le n \le 100$ | $1 \le q \le 100$ | | 2 | 27 | $1 \le a, b \le 3000$ | $2 \le n \le 3000$ | $1 \le q \le 3000$ | | 3 | 23 | $1 \le a, b \le 3000$ | $2 \le n \le 100\,000$ | $1 \le q \le 100\,000$ | | 4 | 22 | $1 \le a, b \le 150\,000$ | $2 \le n \le 150\,000$ | $1 \le q \le 150\,000$ |