구역 나누기

주 또는 도의 모든 주택에 대한 등록부가 주어졌을 때, 주소 범위에 속하는 모든 주택이 구역 안이나 경계에 포함되도록 하는 축에 평행한 정사각형 구역의 최소 크기를 구하고 싶다. 구역 규정은 다소 관대하여 범위에서 주택 하나를 무시하면 구역을 더 작게 만들 수 있다.

주소는 1..n 범위의 정수로 주어진다. 구역 요청은 연속된 주택 범위로 주어진다. 유효한 구역이란 범위 내 모든 점을 포함하면서 최대 하나를 무시할 수 있는 가장 작은 축에 평행한 정사각형이다.

주택의 (x, y) 위치와 구역 요청 목록이 주어졌을 때, 각 요청에 대해 답해야 한다: 구역 요청에 포함된 모든 주택을 포함하면서 최대 하나의 주택을 무시할 수 있는 축에 평행한 정사각형 구역의 한 변의 길이는 얼마인가?

각 입력은 하나의 테스트 케이스로 구성된다. 프로그램은 서로 다른 입력에 대해 여러 번 실행될 수 있다. 각 테스트 케이스는 두 정수 n과 q (1 ≤ n, q ≤ 105)를 포함하는 한 줄로 시작한다. 여기서 n은 주택의 수이고 q는 구역 요청의 수이다.

다음 n개의 줄에는 각각 두 정수 x와 y (−109 ≤ x, y ≤ 109)가 주어지며, 이는 주의 한 주택의 (x, y) 좌표이다. 이 주택의 주소는 입력 순서와 대응된다. 첫 번째 주택의 주소는 1, 두 번째 주택의 주소는 2, 이런 식이다. 두 주택이 같은 위치에 있는 경우는 없다.

다음 q개의 줄에는 두 정수 a와 b (1 ≤ a < b ≤ n)가 주어지며, 이는 주소가 [a..b] 범위(양 끝 포함)인 주택에 대한 구역 요청을 나타낸다.

q개의 줄을 출력한다. 각 줄에는 하나의 구역 요청에 대한 답을 순서대로 출력한다: 주어진 주소의 주택 점 모두를 포함하며, 최대 한 채의 주택을 무시할 수 있을 때, 축에 평행한 가장 작은 정사각형의 한 변의 길이이다.