配点: 5 点
問題文
在二维坐标平面上有不同的 N 点 P_1, P_2, \ldots, P_N ,并且给定点 P_i 的坐标是 (x_i, y_i) 。
下面 Q 查询。
- i (1 \leq i \leq Q) 个查询中,整数 q_i ,所以点 P_{q_i} 和 按字典顺序比较 N 输出点与点之间的曼哈顿距离的最大值。
- 也就是说,点 P_s 和点 P_t 的曼哈顿距离是 \rm{dist}(P_s, P_t) 时,\rm{max}(\rm{dist}(P_{q_i}, P_1), \cdots, \rm{dist}(P_{q_i}, P_N)) 的值。
关于曼哈顿距离的
座標 (x_1, y_1) 和坐标 (x_2, y_2) 之间的曼哈顿距离,|x_1 - x_2| + |y_1 - y_2| 中定义。制約
- 2 \leq N \leq 100000
- 1 \leq Q \leq N
- -10^9 \leq x_i, y_i \leq 10^9
- (x_i, y_i) \neq (x_j, y_j) (1 \leq i < j \leq N)
- 1 \leq q_i \leq N (1 \leq i \leq Q)
- q_i \neq q_j (1 \leq i < j \leq Q)
- 给出的所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N Q x_1 y_1 \vdots x_N y_N q_1 \vdots q_Q
出力
给定的 Q 个查询的答案用换行分隔。 1 请按行输出。
入力例 1
3 3 -1 2 1 1 -2 -3 1 2 3
出力例 1
6 7 7
1 第几个查询关注点 1 。
- 点 1 和点 1 的曼哈顿距离是 |-1 - (-1)| + |2 - 2| = 0
- 点 1 和点 2 的曼哈顿距离是 |-1 - 1| + |2 - 1| = 3
- 点 1 和点 3 的曼哈顿距离是 |-1 - (-2)| + |2 - (-3)| = 6
因此,1 第几个查询中,这些曼哈顿距离的最大值是 6 。
入力例 2
5 3 -2 -2 -1 -1 0 0 1 1 2 2 5 3 1
出力例 2
8 4 8
入力例 3
2 1 -1000000000 -1000000000 1000000000 1000000000 1
出力例 3
4000000000
小心溢出。