题目背景

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

题目描述

自古以来，北方沿海村庄的手工艺人们便在由方格组成的长方形布巾上用珍珠进行刺绣装饰。刺绣的开始是将第一颗珍珠缝在某个方格的中心位置。为了缝上下一颗珍珠，手工艺人会从已经有珍珠的方格向在水平方向或垂直方向相邻的空方格做一针，然后将新的珍珠缝在这针末端方格的中心。这一过程不断重复，直到所有珍珠都缝制完成。

其中一块节日用的珍珠刺绣布如今保存在博物馆中。不幸的是，部分刺绣图案已经遗失，但布巾的结构信息仍被保存下来。博物馆计划修复布巾上的某一个矩形区域，但尚未决定具体修复哪一块。修复某个区域的成本与该区域中连通的图案部分的数量有关。

我们称一部分图案是连通的，如果在不离开该区域的前提下，可以沿着针脚从其中任意一颗珍珠移动到另一颗珍珠。博物馆总是将可以通过针脚互相到达的所有珍珠视为属于同一个连通部分。

你的任务是编写一个程序，对于给定的每个矩形区域，计算其中连通部分的数量。

输入格式

第一行包含两个整数 $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$ 个矩形区域内的连通部分数量。

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

提示

样例解释

下图给出了题目描述中测试用例的示意图，展示了针脚连接形成的珍珠图案结构。

:::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		$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$