Communication Jamming

JOI Country is on a plane. There are N villages, numbered 1 to N. Village i is treated as the point $(i, 0)$. JOI Country is now building communication lines that connect the villages. To prepare for failures, the lines will be built as two systems, called system 1 and system 2.

System k has $M_k$ hubs and $N + M_k - 1$ lines. The hubs of system k are numbered 1 to $M_k$, and hub j is treated as the point $(X_{kj}, Y_{kj})$. Each line of system k connects a village to a hub of system k, or connects two hubs of system k. Each line is treated as the segment between its two endpoints. No two lines share a point except at their endpoints. The y coordinate $Y_{1j}$ of each hub j in system 1 is greater than 0. The y coordinate $Y_{2j}$ of each hub j in system 2 is less than 0.

Two locations can communicate if they are connected through lines, directly or indirectly. In other words, they can communicate if one can travel along the lines from one to the other. Using only the lines of system 1, or using only the lines of system 2, any two villages and hubs can communicate.

The figure below shows an example of the network. Gray circles are hubs of system 1, black circles are hubs of system 2, and white circles are villages.

Figure 1: Example network 1	Figure 2: Example network 2

While planning, we want to know how much attack the network can survive and still keep communication. An external attack is described by two integers A and B ($A \ge 0$, $B \le 0$). The attack destroys every hub with a y coordinate greater than A and every hub with a y coordinate less than B. When a hub is destroyed, communication through that hub is no longer possible.

The information about the villages and each system is given. Then Q queries are given. Each query q is one integer $A_q$, which means that every hub with a y coordinate greater than $A_q$ is destroyed. For each query, find whether all villages can still communicate when additional hubs with y coordinates below some value are also destroyed. That is, find the largest integer $B_q$ ($B_q \le 0$) such that all villages can still communicate after destroying every hub with a y coordinate greater than $A_q$ and every hub with a y coordinate less than $B_q$.

The first line contains four integers N, M1, M2, Q separated by spaces.

The next $M_1 + (N + M_1 - 1)$ lines describe system 1.

• The first $M_1$ lines give, for the i-th line, two integers $X_{1i}$ and $Y_{1i}$.
• The next $N + M_1 - 1$ lines give, for the i-th line, three integers $T_{1i}$, $C_{1i}$, $D_{1i}$ describing line i, where $T_{1i}$ is 1 or 2.
  • If $T_{1i}$ is 1, line i connects village $C_{1i}$ and hub $D_{1i}$ ($1 \le C_{1i} \le N$, $1 \le D_{1i} \le M_1$).
  • If $T_{1i}$ is 2, line i connects hub $C_{1i}$ and hub $D_{1i}$ ($1 \le C_{1i}, D_{1i} \le M_1$, $C_{1i} \ne D_{1i}$).

The information for system 2 follows in the same format, with $M_2 + (N + M_2 - 1)$ lines.

The last Q lines give, for the i-th line, one integer $A_i$.

Print Q lines. The i-th line contains the answer $B_i$ to query i. If the answer is 0, print 0, not -0.

• $1 \le N, M_1, M_2 \le 100000$
• $-1000000000 \le X_{1i} \le 1000000000$ ($1 \le i \le M_1$).
• $-1000000000 \le X_{2i} \le 1000000000$ ($1 \le i \le M_2$).
• $1 \le Y_{1i} \le 1000000000$ ($1 \le i \le M_1$).
• $-1000000000 \le Y_{2i} \le -1$ ($1 \le i \le M_2$).
• For $1 \le i, j \le M_1$ with $i \ne j$, $X_{1i} \ne X_{1j}$ or $Y_{1i} \ne Y_{1j}$.
• For $1 \le i, j \le M_2$ with $i \ne j$, $X_{2i} \ne X_{2j}$ or $Y_{2i} \ne Y_{2j}$.
• $1 \le Q \le 100000$
• $0 \le A_i \le 1000000000$ ($1 \le i \le Q$).
• No two lines share a point except at their endpoints.
• Using only the lines of system 1, or only the lines of system 2, any two villages and hubs can communicate.