很久以前，在萨满之国（Land of the Shamans），每个人都住在高耸入云的豆茎（Sky-High Beanstalk）上。每位萨满都有一个 $0$ 到 $N-1$ 之间的唯一编号 $i$，以及一个海拔值 $H_i$，代表他居住的高度。两个海拔之间的距离是它们差的绝对值。

所有的萨满原本和平共处，直到其中一人偷走了世界闻名的“伟力药水”（Potion of Great Power）的配方。为了掩盖行踪，小偷（Thief）对这片土地施下了诅咒（Curse）：大多数居民不再互相信任……

尽管情况非常困难，但“善良调查员组织”（Order of Good Investigators）还是获得了关于诅咒的以下信息：

• 当诅咒首次生效时，所有人都不再互相信任。
• 诅咒是不稳定的：在每一天的结束（午夜时分），会有一对萨满开始或停止互相信任。
• 不幸的是，每位萨满在任何时候最多只能信任 $D$ 个人。

他们还重建了一份信任关系日志：对于每个夜晚，他们都知道哪一对萨满开始或停止了互相信任。

他们认为小偷将配方低声告诉了一位邪恶萨满（Evil Shaman）。为了避免被发现，他们两人都拜访了各自的一位受信任的朋友。在拜访期间，小偷通过窗户将配方低声告诉了邪恶萨满。（注：这位受信任的朋友当时不一定在家。事实上，他们甚至可能拜访了彼此的家——萨满是很奇怪的。）

幸运的是，低语只能传播很短的距离，所以组织知道小偷和邪恶萨满拜访的那两位受信任的朋友一定住得非常近。

他们请求你协助调查。他们想测试自己的怀疑：如果小偷是 $x$，邪恶萨满是 $y$，且配方是在第 $v$ 天被低语的，那么低语传播的最小距离是多少？也就是说，在第 $v$ 天，对于 $x$ 的某个受信任的朋友 $x'$ 和 $y$ 的某个受信任的朋友 $y'$，$\min(|H_{x'} - H_{y'}|)$ 的最小值是多少？

他们将与你分享所有信息，然后向你提出一系列问题。你需要立即回答每个问题，然后再接收下一个问题。

实现细节

这是一个交互式任务。你需要实现以下函数：

• void init(int N, int D, int H[]) $N$ 是萨满的人数，$D$ 是任何时候一位萨满最多能拥有的受信任朋友数量，$H$ 是一个大小为 $N$ 的数组，其中 $H[i]$ 表示萨满 $i$ 的海拔（$0 \le i < N$）。

• void curseChanges(int U, int A[], int B[]) $U$ 是天数，$A$ 和 $B$ 是大小为 $U$ 的数组，使得 $A[i]$ 和 $B[i]$ 是在第 $i$ 天结束时开始或停止互相信任的萨满对（$0 \le i < U$）。也就是说，如果 $A[i]$ 和 $B[i]$ 在第 $i$ 天互相信任，那么在第 $i+1$ 天他们就不再互相信任，反之亦然。

• int question(int X, int Y, int V) $X$ 是被怀疑的小偷，$Y$ 是被怀疑的邪恶萨满，$V$ 是被怀疑的日期。你应该返回低语从 $X$ 的某个受信任朋友 $x'$ 到 $Y$ 的某个受信任朋友 $y'$ 所需传播的最小距离。 如果有人同时信任 $X$ 和 $Y$（即 $x' = y'$），你应该返回 $0$。 如果 $X$ 或 $Y$ 没有受信任的朋友，返回 $10^9$。

前两个函数将在程序执行开始时各被调用一次，顺序如上。此后，question 函数将被多次调用。设调用次数为 $Q$。

数据范围

• $2 \le N \le 10^5$
• $1 \le D \le 500$
• $0 \le U \le 2 \cdot 10^5$
• $1 \le Q \le 50\,000$
• $0 \le H_i \le 10^9$（对于所有 $0 \le i < N$）
• $0 \le A[j], B[j], X, Y < N$ 且 $X \neq Y$ 且 $A[j] \neq B[j]$（对于所有 $0 \le j < U$）
• $0 \le V \le U$
• 时间限制：3.5 秒
• 内存限制：256 MiB

样例

init(N=6, D=5, H={ 2 , 42 , 1000 , 54 , 68 , 234 });

//Day: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
curseChanges(U=11, A={ 0 , 2 , 3 , 3 , 3 , 1 , 5 , 0 , 3 , 1 , 3 },
             B={ 1 , 0 , 4 , 5 , 5 , 3 , 3 , 5 , 0 , 3 , 5 });

question(X=0, Y=3, V=4) returns 26;
// 说明: |H[1] - H[4]| = 26

question(X=3, Y=0, V=8) returns 0;
// 说明: |H[1] - H[1]| = 0 或 |H[5] - H[5]| = 0

question(X=0, Y=5, V=5) returns 1000000000;
// 说明: Y 在第 5 天没有受信任的朋友

question(X=3, Y=0, V=11) returns 14;
// 说明: |H[4] - H[3]| = 14

图 1 展示了上述示例中问题的答案，图 2 展示了每天的友谊（信任）关系。

图 1：示例中的四个问题示意图

图 2：示例中友谊（信任）关系的演变

子任务