Problem K
Zoning Houses

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?

Input

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 \le n,q \le 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 \le x,y \le 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 \le a < b \le n$), which represents a zoning request for houses with addresses in the range $[a..b]$ inclusive.

Output

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.

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

1
0

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

300
299