You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

dzy 有一个花园，每朵花可以表示为平面直角坐标系上的 $N$ 个点，第 $i$ 个点坐标 $(x_i,y_i)$。定义两朵花之间的距离为它们的切比雪夫距离，即 $dis(u,v)=\max(|x_u-x_v|,|y_u-y_v|)$。

dzy 会向你提出 $Q$ 次询问，第 $i$ 个询问为一个区间 $[l_i,r_i]$，请确定一个 $k(l\le k\le r)$，最大化 $\min_{l\le u<v\le r,u\not=k,v\not=k}dis(u,v)$。即，最大化：删掉一朵花后，区间里花之间距离最小值。

输入格式

第一行一个正整数 $N$；

接下来 $N$ 行，每行两个正整数 $x_i,y_i$；

接下来一行一个正整数 $Q$ 表示询问次数；

接下来 $Q$ 行，每行两个正整数 $l_i,r_i$。

输出格式

$Q$ 行，每行一个整数表示距离最小值。

样例1

输入样例

6
1 2
3 2
5 7
9 9
11 14
12 1
10
1 3
1 4
1 5
1 6
2 4
2 5
2 6
3 5
3 6
4 6

输出样例

5
4
4
4
7
5
5
7
7
13

样例解释

对于第 $1$ 个询问，删掉 $(1,2)$ 或 $(3,2)$ 中任意一个即可；

对于第 $2$ 到 $4$ 个询问，删掉 $(3,2)$ 即可。

样例2

输入样例

10
61128150 17784149
21428280 74148989
868580 46098691
8593771 15734932
88279588 65265965
1405681 91709681
33143481 58940320
15601518 24401692
38310358 66093877
56740702 42674203
15
1 7
2 4
1 9
3 9
2 9
5 7
3 8
6 9
4 6
2 7
5 9
4 8
5 10
2 5
4 10

输出样例

30363759
58414057
8666760
8666760
8666760
86873907
30363759
36904677
86873907
30363759
36904677
32769361
23597221
58414057
8666760

样例 3-6

样例 3 参见 flower03.in/.out，该大样例满足 Subtask 3 限制。

样例 4 参见 flower04.in/.out，该大样例满足 Subtask 4 限制。

样例 5 参见 flower05.in/.out，该大样例满足 Subtask 5 限制。

样例 6 参见 flower06.in/.out，该大样例无特殊性质。

数据范围

$3\le N\le3\times10^4$

$1\le Q\le3\times10^5$

$1\le x_i,y_i\le 10^8$

$1\le l_i<r_i\le N,r_i-l_i\ge2$

保证不存在重合的点。