## MOG Training #7## Ended |

Given a registry of all houses in your state or province, you would like to know the minimum size of an axis-aligned square zone such that every house in a range of addresses lies in the zone or on its border. The zoning is a bit lenient and you can ignore any one house from the range to make the zone smaller.

The addresses are given as integers from $1..n$. Zoning requests are given as a consecutive range of houses. A valid zone is the smallest axis-aligned square that contains all of the points in the range, ignoring at most one.

Given the $(x, y)$ locations of houses in your state or province, and a list of zoning requests, you
must figure out for each request: What is the length of a side of the smallest axis-aligned square
zone that contains all of the houses in the zoning request, possibly ignoring one house?

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line containing two integers $n$ and $q$ $(1 \leq n, q \leq 10^5)$, where $n$ is the number of houses, and $q$ is the number of zoning requests.

The next $n$ lines will each contain two integers, $x$ and $y$ $(-10^9 \leq x, y \leq 10^9)$, which are the $(x,y)$ coordinates of a house in your state or province. The address of this house corresponds with the order in the input. The first house has address $1$, the second house has address $2$, and so on. No two houses will be at the same location.

The next $q$ lines will contain two integers $a$ and $b$ $(1 \leq a \lt b \leq n)$, which represents a zoning
request for houses with addresses in the range $[a..b]$ inclusive.

Output $q$ lines. On each line print the answer to one of the zoning requests, in order: the side length
of the smallest axis-aligned square that contains all of the points of houses with those addresses, if
at most one house can be ignored.

Input

3 2
1 0
0 1
1000 1
1 3
2 3

Output

1
0

Input

4 2
0 0
1000 1000
300 300
1 1
1 3
2 4

Output

300
299