题目背景

很久以前，在一颗遥远的星球上，一种传染性极强的病毒引发了长期疫情。尽管如此，人们仍希望在各国之间旅行。

疫情前，从任意国家前往任意另一个国家都恰好需要 1 天。疫情期间，各国会根据旅客上一站国家的感染率，决定是否要求其隔离。

一个独立机构为每个国家分配了一个 $r$ 值；$r$ 值越大，表示感染率越高。

题目描述

共有 $n$ 个国家。国家 $i$ 的感染率为 $r_i$，隔离时间为 $t_i$。

从国家 $i$ 直接前往国家 $j$：

• 旅行本身需要 1 天；
• 若 $r_i>r_j+m$，抵达国家 $j$ 后还必须隔离 $t_j$ 天；
• 否则不需要隔离。

旅客可以选择经过任意多个中间国家。隔离结束后，才能继续下一段旅程；若当前国家就是最终目的地，隔离时间同样计入总旅行时间。

给定 $q$ 组出发国家和目的国家，求每组询问的最短总旅行时间。

输入格式

第一行包含三个整数 $n,q,m$（$2\le n\le 10^5$，$1\le q\le 10^5$，$0\le m\le 10^9$），分别表示国家数量、询问数量和允许的最大感染率下降值。

第二行包含 $n$ 个整数 $r_1,r_2,\ldots,r_n$，满足

第三行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$（$0\le t_i\le 10^9$），表示在国家 $i$ 隔离所需的天数。

接下来 $q$ 行，每行包含两个整数 $x,y$（$1\le x,y\le n$，$x\ne y$），表示一名旅客从国家 $x$ 出发，最终前往国家 $y$。

输出格式

对每组询问输出一行一个整数，表示最短旅行时间。

样例 1

输入

5 4 1
0 5 6 7 8
3 4 1 5 10
1 4
4 1
4 2
5 2

输出

1
4
2
3

样例 2

输入

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

输出

6
7
1
1