P16137 [ICPC 2018 NAIPC] Zoning Houses

给定你所在州或省所有房屋的登记信息，对于一段地址范围内的房屋，你想知道能够覆盖所有这些房屋（包括边界）的最小轴对齐正方形区域的边长。由于区域规划有一定的灵活性，你可以忽略该范围内的任意一个房屋，从而使覆盖区域更小。 地址以 $1 \dots n$ 的整数给出。规划请求由一段连续的房屋地址范围给出。一个有效的区域是指能够覆盖该范围内所有点（最多可忽略一个点）的最小轴对齐正方形。 给定你所在州或省中每个房屋的 $(x, y)$ 坐标，以及一系列规划请求，对于每个请求，你需要回答：能够覆盖该请求中所有房屋（最多可忽略一个房屋）的最小轴对齐正方形的边长。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^5$），其中 $n$ 是房屋的数量，$q$ 是规划请求的数量。 接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$（$-10^9 \leq x, y \leq 10^9$），表示你所在州或省中一个房屋的 $(x, y)$ 坐标。该房屋的地址与输入顺序对应：第一个房屋的地址为 1，第二个房屋的地址为 2，依此类推。没有两个房屋位于同一位置。 接下来的 $q$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a < b \leq n$），表示一个规划请求，要求覆盖地址在 $[a\dots b]$ 范围内的房屋。

输出 $q$ 行。每行按顺序输出一个规划请求的答案：能够覆盖这些地址上的所有房屋（最多可忽略一个房屋）的最小轴对齐正方形的边长。

翻译由 DeepSeek V3.2 完成