JOI-land exists on a 2D plane. There are $N$ villages, numbered from 1 to $N$. Village $i$ is considered a point at coordinates $(i, 0)$. Currently, JOI-land is planning to develop communication lines to connect the villages. To prepare for potential failures, the communication lines will be developed in two systems, which we call System 1 and System 2.

In System $k$, there are $M_k$ hubs and $N + M_k - 1$ lines. The hubs of System $k$ are numbered from 1 to $M_k$, and hub $j$ is considered a point at coordinates $(X_{kj}, Y_{kj})$. Each line in System $k$ connects a village and a hub of System $k$, or two hubs of System $k$. Each line is considered a line segment connecting its two endpoints. It is guaranteed that any two lines do not share any points other than their endpoints. The $y$-coordinate $Y_{1j}$ of hub $j$ in System 1 is greater than 0. Also, the $y$-coordinate $Y_{2j}$ of hub $j$ in System 2 is less than 0.

Two locations are said to be able to communicate if they are indirectly connected by lines. That is, if one can move from one location to another by repeatedly moving along the lines, then the two locations can communicate. Even considering only the lines of System 1, or only the lines of System 2, any two villages and hubs can communicate.

The figure below shows an example of communication lines. Gray circles represent hubs of System 1, black circles represent hubs of System 2, and white circles represent villages.

Figure 1: Example 1 of communication lines

Figure 2: Example 2 of communication lines

When considering the plan, we want to investigate how much communication is possible under external attacks. An external attack is represented by two numbers $A$ and $B$ ($A \ge 0, B \le 0$), and it is assumed that all hubs with a $y$-coordinate greater than $A$ and all hubs with a $y$-coordinate less than $B$ are destroyed. When a hub is destroyed, communication through it becomes impossible.

Task

Information about the villages and each system is given. Also, $Q$ queries are given. Each query $q$ is represented by a single integer $A_q$, which means that all hubs with a $y$-coordinate greater than $A_q$ are destroyed. For each query, answer how many hubs with a $y$-coordinate less than some value can be destroyed while still allowing communication between all villages. That is, for each query, find the maximum integer $B_q$ ($B_q \le 0$) such that communication between all villages is possible even if all hubs with a $y$-coordinate greater than $A_q$ and all hubs with a $y$-coordinate less than $B_q$ are destroyed.

Input

Read the following input from standard input:

• The first line contains four integers $N, M_1, M_2, Q$ separated by spaces.
• The following $M_1 + (N + M_1 - 1)$ lines contain information about System 1:
  • The first $M_1$ lines, the $i$-th line ($1 \le i \le M_1$), contain two integers $X_{1i}, Y_{1i}$.
  • The following $N + M_1 - 1$ lines, the $i$-th line ($1 \le i \le N + M_1 - 1$), contain three integers $T_{1i}, C_{1i}, D_{1i}$ representing the information of line $i$ ($T_{1i} = 1, 2$):
    • If $T_{1i}$ is 1, line $i$ connects village $C_{1i}$ and hub $D_{1i}$ ($1 \le C_{1i} \le N$ and $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$ and $C_{1i} \neq D_{1i}$).
• The following $M_2 + (N + M_2 - 1)$ lines contain information about System 2:
  • The first $M_2$ lines, the $i$-th line ($1 \le i \le M_2$), contain two integers $X_{2i}, Y_{2i}$.
  • The following $N + M_2 - 1$ lines, the $i$-th line ($1 \le i \le N + M_2 - 1$), contain three integers $T_{2i}, C_{2i}, D_{2i}$ representing the information of line $i$ ($T_{2i} = 1, 2$):
    • If $T_{2i}$ is 1, line $i$ connects village $C_{2i}$ and hub $D_{2i}$ ($1 \le C_{2i} \le N$ and $1 \le D_{2i} \le M_2$).
    • If $T_{2i}$ is 2, line $i$ connects hub $C_{2i}$ and hub $D_{2i}$ ($1 \le C_{2i}, D_{2i} \le M_2$ and $C_{2i} \neq D_{2i}$).
• The following $Q$ lines, the $i$-th line ($1 \le i \le Q$), contain a single integer $A_i$.

Output

Output $Q$ lines to standard output. The $i$-th line ($1 \le i \le Q$) should contain the integer $B_i$ representing the answer to query $i$. If the answer is 0, do not output -0.

Constraints

All input data satisfies the following conditions:

• $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}$ or $Y_{1i} \neq Y_{1j}$ ($1 \le i, j \le M_1$ and $i \neq j$).
• $X_{2i} \neq X_{2j}$ or $Y_{2i} \neq Y_{2j}$ ($1 \le i, j \le M_2$ and $i \neq j$).
• $1 \le Q \le 100\,000$.
• $0 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le Q$).
• Any two lines do not share any points other than their endpoints.
• Even considering only the lines of System 1, or only the lines of System 2, any two villages and hubs can communicate.

Subtasks

Subtask 1 [20 points]

The following conditions are satisfied: $N, M_1, M_2 \le 1\,000$. $Q \le 1\,000$.

Subtask 2 [80 points]

There are no additional constraints.

Examples

Input 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

Output 1

-2

Input 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

Output 2

0
-2
-1
-3