정올국은 평면 상에 존재하는 나라이다. 이 나라에는 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 의 최댓값을 구하는 프로그램을 작성하시오.

통신 방해 timer 2초 memory 256MB

통신 방해 2초 256MB