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$ | 無額外限制 |