P11907 [NHSPC 2023] F. 恐怖的黑色魔物

G 公司最近用黑科技在某个神秘的地方建立了新的研发中心。这座研发中心的形状是长方体，内部共有 $F$ 层楼，每一层楼均有由 $M$ 列 $N$ 行组成的矩形房间。一个房间的位置用三个正整数 $(p, q, r)$ 表示，代表该房间位于研发中心 $p$ 楼的第 $q$ 列第 $r$ 行。 G 公司的员工均可以通过黑科技直接传送到隔壁、楼下或楼上的房间。更明确地说，位于房间 $(p, q, r)$ 的 G 公司员工， 1. 当 $p > 1$ 时，可以传送到房间 $(p-1, q, r)$。 1. 当 $p < F$ 时，可以传送到房间 $(p+1, q, r)$。 1. 当 $q > 1$ 时，可以传送到房间 $(p, q-1, r)$。 1. 当 $q < M$ 时，可以传送到房间 $(p, q+1, r)$。 1. 当 $r > 1$ 时，可以传送到房间 $(p, q, r-1)$。 1. 当 $r < N$ 时，可以传送到房间 $(p, q, r+1)$。 G 公司为了节省员工的用餐休息时间，在其中的 $R$ 个房间开设了餐厅，方便员工在研发中心内直接用餐。但餐厅的食物会滋生一种恐怖的黑色魔物，有一部分的 G 公司员工非常害怕这种恐怖的黑色魔物，因此不敢在这些餐厅用餐。 你的上司 K 先生特别害怕这种恐怖的黑色魔物。他总认为这些恐怖的黑色魔物，也能通过黑科技，在研发中心里自由穿梭。他定义了「黑色恐怖距离」：若一个房间至少须使用 $d$ 次黑科技传送，才能抵达餐厅，则该房间的黑色恐怖距离就是 $d$。对 K 先生来说，黑色恐怖距离越小就越恐怖，因此他每次在研发中心内移动时，都会计算该如何使用黑科技，才能让途中经过的房间，最小的黑色恐怖距离最大。作为 K 先生下属的你，打算编写一个程序，帮助 K 先生快速算出在最不恐怖的路径上，所经过的房间里黑色恐怖距离的最小值。

> $F$ $M$ $N$ > $R$ > $p_1$ $q_1$ $r_1$ > $p_2$ $q_2$ $r_2$ > $\vdots$ > $p_R$ $q_R$ $r_R$ > $Q$ > $a_1$ $b_1$ $c_1$ $x_1$ $y_1$ $z_1$ > $a_2$ $b_2$ $c_2$ $x_2$ $y_2$ $z_2$ > $\vdots$ > $a_Q$ $b_Q$ $c_Q$ $x_Q$ $y_Q$ $z_Q$ * $F$ 代表 G 公司研发中心的层数。 * $M$ 代表 G 公司研发中心的列数。 * $N$ 代表 G 公司研发中心的行数。 * $R$ 代表 G 公司研发中心的餐厅数。 * $(p_i, q_i, r_i)$ 代表 G 公司研发中心内第 $i$ 间餐厅的位置。 * $Q$ 代表 K 先生计划移动的次数。 * $(a_i, b_i, c_i)$ 代表 K 先生计划第 $i$ 次移动的起点。 * $(x_i, y_i, z_i)$ 代表 K 先生计划第 $i$ 次移动的终点。

> $d_1^*$ > $d_2^*$ > $\vdots$ > $d_Q^*$ * $d_i^*$ 代表 K 先生第 $i$ 次移动时，所有可能的路径中，最小黑色恐怖距离的最大值。

### 测试数据限制 * $1 \le F \le 2\times10^5$。 * $1 \le M \le 2\times10^5$。 * $1 \le N \le 2\times10^5$。 * $1 \le FMN \le 2\times10^5$。 * $1 \le R \le FMN$。 * $1 \le p_i \le F$。 * $1 \le q_i \le M$。 * $1 \le r_i \le N$。 * $1 \le Q \le 2\times10^5$。 * $1 \le a_i \le F$。 * $1 \le b_i \le M$。 * $1 \le c_i \le N$。 * $1 \le x_i \le F$。 * $1 \le y_i \le M$。 * $1 \le z_i \le N$。 * 对任意 $i, j \in \{1, 2, \ldots, R\}$，若 $i \ne j$，则 $(p_i, q_i, r_i) \ne (p_j, q_j, r_j)$。 * 输入的数皆为整数。 ### 评分说明 本题共有五组子任务，条件限制如下所示。 每一组可有一或多个测试数据，该组所有测试数据皆需答对才可获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | $6$ | $F = R = 1, MN \le 100, Q \le 100$ | | 2 | $21$ | 对任意 $i \in \{1, 2, \ldots, Q\}$，均有 $(a_i, b_i, c_i) = (x_i, y_i, z_i)$ | | 3 | $4$ | $FMN \le 3000$ | | 4 | $25$ | $Q = 1$ | | 5 | $44$ | 无额外限制 |