Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

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 \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

Sample test(s)