单点时限: 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)$。洪水会蔓延，这代表着：
此处的距离为曼哈顿距离。
现在 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$ 行，每行一个整数，表示答案。
1 3 200000000 1 1 100000000 100000000 1 1 100000000 1 1 100000000 1 1 100000000 100000000
1 100000000 199999999
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
200000174 200000182 200000212 200000223 200000225 200000173 200000238 200000220 200000188 200000190