题目描述

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)$。
• 输入的数皆为整数。

评分说明

本题共有五组子任务，条件限制如下所示。 每一组可有一或多个测试数据，该组所有测试数据皆需答对才可获得该组分数。