통신 방해

JOI 국은 평면 위에 있다. 마을은 N개이며 1부터 N까지 번호가 붙어 있다. 마을 i는 좌표 $(i, 0)$의 점으로 본다. 지금 JOI 국은 마을을 잇는 통신 회선을 정비하려고 한다. 장애에 대비해 통신 회선은 두 계통으로 깐다. 이를 계통 1과 계통 2라고 부른다.

계통 k에는 허브가 $M_k$개 있고 회선은 $N + M_k - 1$개 있다. 계통 k의 허브에는 1부터 $M_k$까지 번호가 붙어 있으며, 허브 j는 좌표 $(X_{kj}, Y_{kj})$의 점으로 본다. 계통 k의 각 회선은 마을과 계통 k의 허브를 잇거나, 계통 k의 허브끼리 잇는다. 각 회선은 두 끝점을 잇는 선분으로 본다. 어떤 두 회선도 끝점을 제외하면 공통된 점이 없다. 계통 1 허브의 y 좌표 $Y_{1j}$는 0보다 크다. 계통 2 허브의 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 좌표가 어떤 값보다 작은 허브까지 파괴되어도 모든 마을 사이의 통신이 가능한지 답하라. 즉 y 좌표가 $A_q$보다 큰 허브와 y 좌표가 $B_q$보다 작은 허브를 모두 파괴해도 모든 마을 사이의 통신이 가능한 가장 큰 정수 $B_q$ ($B_q \le 0$)를 구하라.

첫 줄에 정수 N, M1, M2, Q가 공백으로 구분되어 주어진다.

이어서 계통 1의 정보가 $M_1 + (N + M_1 - 1)$줄에 주어진다.

• 처음 $M_1$줄의 i번째 줄에는 정수 $X_{1i}$, $Y_{1i}$가 주어진다.
• 다음 $N + M_1 - 1$줄의 i번째 줄에는 회선 i를 나타내는 정수 $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} \ne D_{1i}$).

계통 2의 정보도 같은 형식으로 $M_2 + (N + M_2 - 1)$줄에 주어진다.

마지막 Q줄의 i번째 줄에는 정수 $A_i$가 하나씩 주어진다.

Q줄을 출력한다. i번째 줄에는 질의 i에 대한 답 $B_i$를 출력한다. 답이 0이면 -0이 아니라 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$).
• $i \ne j$인 $1 \le i, j \le M_1$에 대해 $X_{1i} \ne X_{1j}$ 또는 $Y_{1i} \ne Y_{1j}$이다.
• $i \ne j$인 $1 \le i, j \le M_2$에 대해 $X_{2i} \ne X_{2j}$ 또는 $Y_{2i} \ne Y_{2j}$이다.
• $1 \le Q \le 100000$
• $0 \le A_i \le 1000000000$ ($1 \le i \le Q$).
• 어떤 두 회선도 끝점을 제외하면 공통된 점이 없다.
• 계통 1의 회선만 고려해도, 계통 2의 회선만 고려해도 임의의 두 마을과 허브는 서로 통신할 수 있다.