4040. 洪水

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 要在一个 $10^8 \times 10^8$ 的网格上旅行。

我们用二元组 $(x, y)$ 表示网格中第 $x$ 行第 $y$ 列的点。某个正整数时刻,Cuber 会在某个点出现。之后每过一个时刻,Cuber QQ 都可以从 $(x, y)$ 移动到 $(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)$ 中的一个点,也可以不移动。当然,Cuber QQ 不能移动到网格之外。

但是会发生 $n$ 次洪水。第 $i$ 次洪水会在第 $t_i$ 个时刻出现在位置 $(u_i, v_i)$。洪水会蔓延,这代表着:

  • 在时刻 $t_i$,Cuber QQ 所在的位置不能为 $(u_i, v_i)$;
  • 在时刻 $t_i + 1$,Cuber QQ 所在的位置与 $(u_i, v_i)$ 的距离不能 $\le 1$;
  • 在时刻 $t_i + 2$,Cuber QQ 所在的位置与 $(u_i, v_i)$ 的距离不能 $\le 2$;
  • ......

此处的距离为曼哈顿距离

现在 Cuber QQ 要预先制定出行计划。Cuber QQ 会旅行 $q$ 次,第 $i$ 次起点为 $(a_i, b_i)$,终点为 $(c_i, d_i)$。Cuber 想知道,他最迟在哪个时刻出发(即从起点出现)才能保证抵达终点。保证在时刻 $1$ 出发 Cuber QQ 可以抵达终点。

输入格式

第一行两个整数 $n, q$($1 \le n \le 100, 1 \le q \le 10^5$)。

接下来 $n$ 行,每行三个整数 $t_i, x_i, y_i$($2 \times 10^8 \le t_i \le 4 \times 10^8, 1 \le x_i, y_i \le 10^8$)。

接下来 $q$ 行,每行四个整数 $a_i, b_i, c_i, d_i$($1 \le a_i, b_i, c_i, d_i \le 10^8, (a_i, b_i) \neq (c_i, d_i))$。

保证所有洪水坐标不同。

输出格式

输出 $q$ 行,每行一个整数,表示答案。

样例

Input
1 3
200000000 1 1
100000000 100000000 1 1
100000000 1 1 100000000
1 1 100000000 100000000
Output
1
100000000
199999999
Input
5 10
200000223 33 37
200000252 54 9
200000369 80 62
200000270 49 55
200000217 50 78
60 12 91 71
41 85 63 28
66 30 86 64
42 11 67 28
6 51 10 89
42 43 98 83
10 96 2 70
58 64 92 24
57 23 35 38
63 15 43 49
Output
200000174
200000182
200000212
200000223
200000225
200000173
200000238
200000220
200000188
200000190

118 人解决,125 人已尝试。

125 份提交通过,共有 189 份提交。

1.9 EMB 奖励。

创建: 10 月,2 周前.

修改: 9 月,4 周前.

最后提交: 3 月,3 周前.

来源: EOJ Monthly 2021.1

题目标签