가장 큰 정사각형

그레테에게 꼭짓점이 $n$개인 다각형이 있다. 다각형의 모든 변은 좌표축과 평행하고, 인접한 두 변은 서로 수직이다. 이 다각형은 단순 다각형이어서 자기 교차도, 자기 접촉도 없다.

그레테는 $m$개의 질의를 받는다. 각 질의에서는 다각형 내부의 점 $(u_i, v_i)$가 주어진다. 그레테는 이 점을 왼쪽 아래 꼭짓점으로 하고, 다각형 내부에 들어가는 가장 큰 정사각형의 한 변의 길이를 구하려 한다.

입력은 여러 개의 테스트 케이스로 이루어지며 파일의 끝(EOF)에서 끝난다. 각 테스트 케이스의 형식은 다음과 같다.

첫 줄에는 꼭짓점의 개수 $n$과 질의의 개수 $m$이 주어진다.

다음 $n$개의 줄에는 다각형의 꼭짓점 좌표 $x_i$, $y_i$가 반시계 방향 순서로 주어진다.

그다음 $m$개의 줄에는 각 질의의 왼쪽 아래 꼭짓점 좌표 $u_i$, $v_i$가 주어진다.

각 질의마다 정수 하나를 한 줄에 출력한다. 그 값은 질의 점을 왼쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변의 길이이다.

• $4 \leq n \leq 2 \times 10^5$
• $1 \leq m \leq 2 \times 10^5$
• $-10^8 \leq x_i, y_i, u_i, v_i \leq 10^8$
• $n$의 합과 $m$의 합은 모두 $2 \times 10^6$을 넘지 않는다.