P4348 [CERC2015] Cow Confinement

附近的一个牧场可以表示为一个由 $10^6$ 行和 $10^6$ 列组成的矩形网格。行从上到下用整数 $1$ 到 $10^6$ 编号，列从左到右用整数 $1$ 到 $10^6$ 编号。 一群共 $n$ 头牛分散在网格中，每头牛占据一个单位方格。牧场中还包含 $m$ 朵蒲公英花（牛喜欢的花），同样每朵花占据一个单位方格。此外，牧场包含 $p$ 个栅栏，每个栅栏是一个沿单位方格边缘延伸的矩形。栅栏之间不会相交或接触。然而，一个栅栏内部可能包含其他栅栏。 由于不利的风向条件，牛只能朝两个方向移动——向下或向右。牛可以经过被其他牛或花占据的方格，但不能穿过栅栏。 对于每头牛，求从它当前位置可以到达的花朵总数。

输入包含三个部分——第一部分描述栅栏，第二部分描述花朵，第三部分描述牛。 第一部分的第一行包含一个整数 $f$（$0 \leq f \leq 200000$）——栅栏的数量。接下来的 $f$ 行每行包含四个整数 $r_1, c_1, r_2, c_2$（$1 \leq r_1, c_1, r_2, c_2 \leq 10^6$），描述一个栅栏——$r_1$ 和 $c_1$ 是栅栏内部左上角方格的坐标（行和列），而 $r_2$ 和 $c_2$ 是栅栏内部右下角方格的坐标。任意两个栅栏不会相交或接触。 第二部分的第一行包含一个整数 $m$（$0 \leq m \leq 200000$）——花朵的数量。接下来的第 $k$ 行包含两个整数 $r$ 和 $c$（$1 \leq r, c \leq 10^6$）——第 $k$ 朵花的位置。任意两朵花不会占据同一位置。 第三部分的第一行包含一个整数 $n$（$1 \leq n \leq 200000$）——牛的数量。接下来的第 $k$ 行包含两个整数 $r$ 和 $c$（$1 \leq r, c \leq 10^6$）——第 $k$ 头牛的位置。任意两头牛不会占据同一位置，且没有花和牛会占据同一位置。

输出应包含 $n$ 行。第 $k$ 行应包含一个整数——从第 $k$ 头牛的位置可以到达的花朵总数。

样例图示：  Central Europe Regional Contest 2015 Problem C 翻译由 DeepSeek V3 完成