题目描述

G 公司最近用黑科技在某個神秘的地方建立了新的研發總部。這座研發總部的形狀是個長方體，內部共有 $F$ 層樓，每一層樓均有形狀大小相同且由 $M$ 列 $N$ 行組成的矩形房間。一個房間的位置以三個正整數 $(p, q, r)$ 表示，代表該房間位於研發總部 $p$ 樓的第 $q$ 列第 $r$ 行。

G 公司的員工均可以透過黑科技直接傳送至隔壁、樓下或樓上的房間。更明確地說，位於房間 $(p, q, r)$ 的 G 公司員工，

1. 當 $p > 1$ 時，可傳送至房間 $(p-1, q, r)$。
2. 當 $p < F$ 時，可傳送至房間 $(p+1, q, r)$。
3. 當 $q > 1$ 時，可傳送至房間 $(p, q-1, r)$。
4. 當 $q < M$ 時，可傳送至房間 $(p, q+1, r)$。
5. 當 $r > 1$ 時，可傳送至房間 $(p, q, r-1)$。
6. 當 $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$ 次移動時，所有可能的路徑中，最小黑色恐怖距離的最大值。

3 3 3
3
1 1 1
2 2 2
3 3 3
4
1 3 3 3 1 1
1 2 2 3 2 2
1 2 3 1 2 3
1 1 1 3 3 3

2
1
2
0

1 1 3
1
1 1 2
1
1 1 1 1 1 3

0

提示

測資限制

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