#5113. 「JOISC 2013 Day1」通信干扰

题目描述

题目译自 JOISC 2013 Day1 T3 「通信妨害」。

JOI 国是一个位于平面上的国家，境内有 $N$ 个村庄，分别编号为 $1$ 到 $N$。你可以将村庄 $i$ 视为位于坐标 $(i, 0)$ 的点。目前，JOI 国计划铺设连接各个村庄的通信线路。为了应对可能的故障，通信线路将分为两套系统，分别称为系统 1 和系统 2。

对于系统 $k$ ($k=1, 2$)，设有 $M_{k}$ 个通信枢纽，以及 $N + M_{k} - 1$ 条通信线路。系统 $k$ 的枢纽编号为 $1$ 到 $M_{k}$，枢纽 $j$ 位于坐标 $(X_{kj}, Y_{kj})$。系统 $k$ 的每条线路连接一个村庄与系统 $k$ 的枢纽，或连接系统 $k$ 的两个枢纽，视为连接两端的线段。题目保证任意两条线路除了端点外不会相交。
系统 $1$ 的枢纽 $j$ 的 $y$ 坐标 $Y_{1j}$ 大于 $0$，而系统 $2$ 的枢纽 $j$ 的 $y$ 坐标 $Y_{2j}$ 小于 $0$。

我们说两个地点能够通信，意味着它们通过线路直接或间接相连，即可以通过沿线路移动从一个地点到达另一个地点。无论是仅考虑系统 $1$ 的线路，还是仅考虑系统 $2$ 的线路，任意两个村庄或枢纽之间都能通信。

下图展示了通信线路的示例，灰色圆圈代表系统 $1$ 的枢纽，黑色圆圈代表系统 $2$ 的枢纽，白色圆圈代表村庄。

在制定计划时，JOI 国希望评估通信系统在遭受外部攻击时的稳定性。外部攻击由两个参数 $A$, $B$ ($A \geq 0$, $B \leq 0$) 定义，表示摧毁所有 $y$ 坐标大于 $A$ 的枢纽和所有 $y$ 坐标小于 $B$ 的枢纽。枢纽被摧毁后，无法通过该枢纽进行通信。

给定村庄和两套系统的信息，以及 $Q$ 个查询，每个查询 $q$ 提供一个整数 $A_{q}$，表示摧毁所有 $y$ 坐标大于 $A_{q}$ 的枢纽。
你需要回答：在此情况下，$y$ 坐标小于多少的枢纽可以被摧毁，同时仍保证所有村庄之间能够通信。
换言之，求最大的整数 $B_{q}$ ($B_{q} \leq 0$)，使得摧毁所有 $y$ 坐标大于 $A_{q}$ 的枢纽和所有 $y$ 坐标小于 $B_{q}$ 的枢纽后，仍然能保持所有村庄之间的通信。

---

输入格式

从标准输入中读取以下数据：

• 第一行包含四个整数 $N$, $M_{1}$, $M_{2}$, $Q$，用空格分隔。
• 接下来 $M_{1} + (N + M_{1} - 1)$ 行描述系统 1 的信息：
  • 前 $M_{1}$ 行中，第 $i$ ($1 \leq i \leq M_{1}$) 行包含两个整数 $X_{1i}$, $Y_{1i}$。
  • 接着 $N + M_{1} - 1$ 行中，第 $i$ ($1 \leq i \leq N + M_{1} - 1$) 行包含三个整数 $T_{1i}$, $C_{1i}$, $D_{1i}$ ($T_{1i}=1, 2$)，表示线路 $i$ 的信息：
    • 若 $T_{1i}=1$，线路 $i$ 连接村庄 $C_{1i}$ 和枢纽 $D_{1i}$ ($1 \leq C_{1i} \leq N$, $1 \leq D_{1i} \leq M_{1}$)。
    • 若 $T_{1i}=2$，线路 $i$ 连接枢纽 $C_{1i}$ 和枢纽 $D_{1i}$ ($1 \leq C_{1i}, D_{1i} \leq M_{1}$, $C_{1i} \neq D_{1i}$)。
• 接下来 $M_{2} + (N + M_{2} - 1)$ 行描述系统 2 的信息：
  • 前 $M_{2}$ 行中，第 $i$ ($1 \leq i \leq M_{2}$) 行包含两个整数 $X_{2i}$, $Y_{2i}$。
  • 接着 $N + M_{2} - 1$ 行中，第 $i$ ($1 \leq i \leq N + M_{2} - 1$) 行包含三个整数 $T_{2i}$, $C_{2i}$, $D_{2i}$ ($T_{2i}=1,2$)，表示线路 $i$ 的信息：
    • 若 $T_{2i}=1$，线路 $i$ 连接村庄 $C_{2i}$ 和枢纽 $D_{2i}$ ($1 \leq C_{2i} \leq N$, $1 \leq D_{2i} \leq M_{2}$)。
    • 若 $T_{2i}=2$，线路 $i$ 连接枢纽 $C_{2i}$ 和枢纽 $D_{2i}$ ($1 \leq C_{2i}, D_{2i} \leq M_{2}$, $C_{2i} \neq D_{2i}$)。
• 最后 $Q$ 行中，第 $i$ ($1 \leq i \leq Q$) 行包含一个整数 $A_{i}$。

---

输出格式

在标准输出中输出 $Q$ 行，第 $i$ ($1 \leq i \leq Q$) 行输出一个整数 $B_{i}$，作为查询 $i$ 的答案。
注意，若答案为 $0$，不得输出 $-0$。

---

样例 1

输入

4 3 3 1
1 1
3 2
2 3
1 1 1
1 2 1
1 3 2
1 4 2
2 1 3
2 2 3
3 -1
2 -2
1 -3
1 1 3
1 2 2
1 3 1
1 4 1
2 1 2
2 2 3
2

输出

-2

此输入样例对应问题描述中的例 1。

---

样例 2

输入

6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0

输出

0
-2
-1
-3

此输入样例对应问题描述中的例 2。

---

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N, M_{1}, M_{2} \leq 100000$
• $-1000000000 \leq X_{1i} \leq 1000000000$ ($1 \leq i \leq M_{1}$)
• $-1000000000 \leq X_{2i} \leq 1000000000$ ($1 \leq i \leq M_{2}$)
• $1 \leq Y_{1i} \leq 1000000000$ ($1 \leq i \leq M_{1}$)
• $-1000000000 \leq Y_{2i} \leq -1$ ($1 \leq i \leq M_{2}$)
• $X_{1i} \neq X_{1j}$ 或 $Y_{1i} \neq Y_{1j}$ ($1 \leq i, j \leq M_{1}$, $i \neq j$)
• $X_{2i} \neq X_{2j}$ 或 $Y_{2i} \neq Y_{2j}$ ($1 \leq i, j \leq M_{2}$, $i \neq j$)
• $1 \leq Q \leq 100000$
• $0 \leq A_{i} \leq 1000000000$ ($1 \leq i \leq Q$)
• 任意两条线路除了端点外不共点。
• 仅考虑系统 $1$ 的线路或仅考虑系统 $2$ 的线路时，任意两个村庄及枢纽都能通信。

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

子任务	分值	附加限制
1	20	$N, M_{1}, M_{2} \leq 1000$, $Q \leq 1000$
2	80	无附加限制

---