JOI 国位于平面上。共有 $N$ 个村庄，编号为 $1$ 到 $N$。村庄 $i$ 被视为坐标为 $(i, 0)$ 的点。目前，JOI 国计划建设连接这些村庄的通信线路。为了应对故障，通信线路将分为两个系统进行建设，分别称为系统 1 和系统 2。

系统 $k$ 包含 $M_k$ 个集线器（hub）和 $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 的集线器，白色圆圈表示村庄。

图 1: 通信线路示例 1

图 2: 通信线路示例 2

在评估计划时，我们想调查在受到外部攻击时，通信在多大程度上仍然可行。外部攻击由两个数 $A, B$ ($A \ge 0, B \le 0$) 表示，假设攻击会摧毁所有 $y$ 坐标大于 $A$ 的集线器以及所有 $y$ 坐标小于 $B$ 的集线器。当集线器被摧毁时，经由该集线器的通信将无法进行。

题目描述

给定村庄和各系统的信息。此外，给定 $Q$ 个查询。每个查询 $q$ 由一个整数 $A_q$ 表示，意味着所有 $y$ 坐标大于 $A_q$ 的集线器都被摧毁。对于每个查询，请回答：在上述条件下，还可以允许摧毁多少个 $y$ 坐标小于某个值的集线器，使得所有村庄之间仍然可以通信？即，求出一个最大的整数 $B_q$ ($B_q \le 0$)，使得即使摧毁了所有 $y$ 坐标大于 $A_q$ 的集线器和所有 $y$ 坐标小于 $B_q$ 的集线器，所有村庄之间仍然可以通信。

输入格式

从标准输入读取以下内容：

• 第 1 行包含 4 个整数 $N, M_1, M_2, Q$，以空格分隔。
• 接下来的 $M_1 + (N + M_1 - 1)$ 行包含系统 1 的信息：
  • 前 $M_1$ 行的第 $i$ 行 ($1 \le i \le M_1$) 包含两个整数 $X_{1i}, Y_{1i}$。
  • 接下来的 $N + M_1 - 1$ 行的第 $i$ 行 ($1 \le i \le N + M_1 - 1$) 包含表示线路 $i$ 信息的 3 个整数 $T_{1i}, C_{1i}, D_{1i}$ ($T_{1i} = 1, 2$)：
    • 当 $T_{1i} = 1$ 时，线路 $i$ 连接村庄 $C_{1i}$ 和集线器 $D_{1i}$ ($1 \le C_{1i} \le N$ 且 $1 \le D_{1i} \le M_1$)。
    • 当 $T_{1i} = 2$ 时，线路 $i$ 连接集线器 $C_{1i}$ 和集线器 $D_{1i}$ ($1 \le C_{1i}, D_{1i} \le M_1$ 且 $C_{1i} \neq D_{1i}$)。
• 接下来的 $M_2 + (N + M_2 - 1)$ 行包含系统 2 的信息：
  • 前 $M_2$ 行的第 $i$ 行 ($1 \le i \le M_2$) 包含两个整数 $X_{2i}, Y_{2i}$。
  • 接下来的 $N + M_2 - 1$ 行的第 $i$ 行 ($1 \le i \le N + M_2 - 1$) 包含表示线路 $i$ 信息的 3 个整数 $T_{2i}, C_{2i}, D_{2i}$ ($T_{2i} = 1, 2$)：
    • 当 $T_{2i} = 1$ 时，线路 $i$ 连接村庄 $C_{2i}$ 和集线器 $D_{2i}$ ($1 \le C_{2i} \le N$ 且 $1 \le D_{2i} \le M_2$)。
    • 当 $T_{2i} = 2$ 时，线路 $i$ 连接集线器 $C_{2i}$ 和集线器 $D_{2i}$ ($1 \le C_{2i}, D_{2i} \le M_2$ 且 $C_{2i} \neq D_{2i}$)。
• 接下来的 $Q$ 行的第 $i$ 行 ($1 \le i \le Q$) 包含一个整数 $A_i$。

输出格式

输出 $Q$ 行到标准输出。第 $i$ 行 ($1 \le i \le Q$) 输出表示查询 $i$ 答案的整数 $B_i$。 如果答案为 $0$，则不得输出 $-0$。

数据范围

所有输入数据满足以下条件：

• $1 \le N, M_1, M_2 \le 100\,000$。
• $-1\,000\,000\,000 \le X_{1i} \le 1\,000\,000\,000$ ($1 \le i \le M_1$)。
• $-1\,000\,000\,000 \le X_{2i} \le 1\,000\,000\,000$ ($1 \le i \le M_2$)。
• $1 \le Y_{1i} \le 1\,000\,000\,000$ ($1 \le i \le M_1$)。
• $-1\,000\,000\,000 \le Y_{2i} \le -1$ ($1 \le i \le M_2$)。
• $X_{1i} \neq X_{1j}$ 或 $Y_{1i} \neq Y_{1j}$ ($1 \le i, j \le M_1$ 且 $i \neq j$)。
• $X_{2i} \neq X_{2j}$ 或 $Y_{2i} \neq Y_{2j}$ ($1 \le i, j \le M_2$ 且 $i \neq j$)。
• $1 \le Q \le 100\,000$。
• $0 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le Q$)。
• 任意两条线路除了端点外没有公共点。
• 无论是仅考虑系统 1 的线路，还是仅考虑系统 2 的线路，任意两个村庄及集线器之间都是可以通信的。

子任务

子任务 1 [20 点]

满足以下条件： $N, M_1, M_2 \le 1\,000$。 $Q \le 1\,000$。

子任务 2 [80 点]

没有额外限制。

样例

样例输入 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

样例输出 1

-2

样例输入 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

样例输出 2

0
-2
-1
-3