国际异常 - 문제

很久很久以前，在遥远的一个星球上，一种高度传染性的病毒引发了一场持久的大流行。

尽管如此，人们仍然希望在暑假期间在国家之间旅行。在过去的美好时光里，从任何国家旅行到任何其他国家都需要整整 1 天。然而，在大流行期间，某些国家不希望接收来自感染率较高地区的旅行者，因此他们要求旅行者隔离一定天数，然后才允许他们继续旅程或开始度假。

为了保持一切公平，一个独立的“准确大流行分类局”成立了。他们根据每个国家的感染率，为每个国家分配了一个 $r$ 值。较高的 $r$ 值表示较高的感染率。

每个国家都要求游客进行隔离，如果他们刚刚来自的国家的 $r$ 值显著高于该国自身的 $r$ 值。具体来说，当你想要从国家 $i$ 旅行到国家 $j$ 时，如果 $r_i > r_j + m$，你将必须隔离 $t_j$ 天。

使用 canva.com 生成，提示词为“背着背包、戴着口罩在山前的旅行者”。

考古学家发现了 $q$ 名游客在 $n$ 个国家之间旅行的证据。对于每位游客，起点和终点都是已知的。剩下需要回答的问题是：每位游客的最短旅行时间是多少？

输入包含以下内容：

第一行包含三个整数 $n$、$q$ 和 $m$（$2 \le n \le 10^5$，$1 \le q \le 10^5$，$0 \le m \le 10^9$），分别表示国家的数量、游客的数量，以及在旅行到感染率较低的国家时，两个 $r$ 值之间允许的最大差值。
第二行包含 $n$ 个整数 $r_1, \dots, r_n$（$0 \le r_1 \le \dots \le r_n \le 10^9$），表示每个国家的 $r$ 值。
第三行包含 $n$ 个整数 $t_1, \dots, t_n$（对于所有 $i$，有 $0 \le t_i \le 10^9$），表示旅行到 $r$ 值显著较低的国家时，所需的隔离天数。
接下来 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$，$x \neq y$），表示一名游客从国家 $x$ 出发，最终目的地为 $y$。

对于每位游客，按照他们在输入中出现的顺序，输出他们从出发国到目的地国的最短旅行时间（以天为单位）。

5 4 10
0 8 20 25 30
5 11 13 6 3
5 1
5 2
5 3
5 4

QOJ.ac