정올국은 평면 상에 존재하는 나라이다. 이 나라에는 N 개의 도시가 있으며 각 도시는 1 부터  N 까지의 번호로 불린다.

 

도시 i의 좌표는 (i, 0)에 존재하는 점이라고 가정한다.

현재 정올국에는 각 도시를 연결하는 통신 회선이 존재한다.

통신 장애에 대비해서 통신 회선은 2 개의 계통장비를 이용하여 이중 연결로 강화될 예정이다.

이중으로 구성될 장치를 계통장비1 과 계통장비2 라고 한다.

 

계통장비k(1 <= k <= 2)에는 허브가 Mk개 존재하고 이들을 연결하는 회선의 수는 n + Mk - 1 개가 된다. 

계통장비k 의 허브는 1 부터 Mk 까지의 번호를 부여하고, 허브 j 는 좌표(Xkj, Ykj)에 존재하는 점이라고 가정한다.

 

계통장비k 의 각 회선은 도시와 허브 또는 허브끼리를 연결하고 있다.각 회선은 하나의 선분이다.

계통장비1 의 허브 j 의 y 좌표 Y1j 는 0 보다 크다.

계통장비2 의 허브 j 의 y 좌표 Y2j 는 0 보다 작다.

즉, 계통장비1 의 허브들은 y 축으로 양의 방향에 설치되고, 계통장비2 의 허브들은 y 축으로 음의 방향에 설치된다.

 

어느 2 개의 도시를 통신으로 연결하려면, 각각의 도시가 회선으로 연결되어 있어야 한다.

즉, 회선을 따라 이동을 반복하여 한 쪽 지점으로부터 다른 쪽 지점까지 이동할 수 있다면, 그 2지점은 통신할 수 있다.

 

계통장비1 의 회선 혹은 계통장비2의 회선 중 어느 한 쪽 회선으로 연결되면 통신할 수 있다.

아래 그림들은 통신회선의 예이다. 회색의 원은 계통장비1 의 허브들을, 검은 원은 계통장비2 의 허브들을 의미하고, 흰색의 원은 도시를 나타낸다.

 

     

만약 외부로 부터 공격에 통신망이 얼마나 버틸 수 있을지 궁금해졌다.

외부로부터의 공격은 2 개의 정수 a, b(a>=0, b<=0)으로 표현된다.

y 좌표가 a 보다 큰 모든 허브와 y 좌표가 b 보다 작은 모든 허브는 파괴된다고 한다.

허브들이 파괴되면 그 허브를 경유하는 통신은 불가능하게 된다.

 

도시와 각 허브들의 정보가 주어질 때, 또 Q 개의 쿼리가 주어진다. 각 쿼리는 공격을 나타낸다.

 

각 쿼리는 정수 a 가 입력으로 들어온다.

이 쿼리에 대해서 모든 도시가 통신하기 위해 필요한 b 의 최댓값을 구하는 프로그램을 작성하시오. 

 

첫 번째 줄에는 n, M1, M2, Q 가 공백으로 구분되어 입력된다. 두 번째 줄부터 M1 줄에 걸쳐 계통장비1의 허브들의 위치를 나타내는 값 Xi, Yi 값이 공백으로 구분되어 입력된다. 다음 줄부터 (N + M1 - 1)줄에 걸쳐서 회선의 정보 t, c, d 가 공백으로 구분되어 주어진다. 만약 t 값이 1 이라면 도시 c 와 허브 d 를 연결한다는 의미이고, 2 라면 허브 c 와 허브 d 를 연결한다는 의미이다. 다음 줄부터 M2 줄에 걸쳐서 계통장비2의 허브들의 위치 Xi, Yi 가 공백으로 구분되어 주어진다. 다음 줄부터 (N + M2 - 1)줄에 걸쳐서 회선의 정보 t, c, d 가 공백으로 구분되어 입력된다. t, c, d 등의 각 값의 의미는 계통장비1과 2와 같다.다음 줄부터 Q 개의 줄에 걸쳐서 한 줄에 하나의 정수 A_i 가 입력된다. 1 <= n, M1, M2 <= 100,000 1 <= Q <= 100,000 -1,000,000,000 <= Xi, Yi <= 1,000,000,000 0 <= Ai <= 1,000,000,000 * 임의의 2 개의 회선은 교차하지 않는다. (끝점 이외에는 공유하지 않는다.) < 제약 사항 > 입력 데이터의 20% 는 n, M1, M2 <= 1,000 , Q <= 1,000 이다. 입력 데이터의 80% 는 추가 제약이 없다.

각 쿼리에 대해서 모든 도시가 통신할 수 있는 b의 최댓값을 출력한다. 만약 답이 0이 될 경우에는 "-0"을 출력하지 않도록 주의한다.

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

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