국제 이상 이동

아주 먼 옛날 어느 행성에서, 전염성이 매우 강한 바이러스가 오랫동안 이어지는 대유행을 일으켰다.

그럼에도 사람들은 여름 휴가를 위해 나라 사이를 여행하고 싶어 했다. 대유행 이전에는 어느 나라에서 다른 어느 나라로 가든 꼬박 하루가 걸렸다. 그러나 대유행 중에는 일부 나라가 감염률이 더 높은 지역에서 오는 여행자를 받지 않으려 했다. 그래서 이런 나라들은 여행을 계속하거나 휴가를 시작하기 전에 여행자에게 일정 일수 동안 격리하도록 요구했다.

공정을 지키기 위해 독립 기관인 정확한 팬데믹 분류국이 감염률에 따라 각 나라에 $r$ 값을 부여했다. $r$ 값이 높을수록 감염률이 높다는 뜻이다.

각 나라는 여행자가 방금 떠나온 나라의 $r$ 값이 자기 나라보다 확실히 높으면 격리를 요구한다. 구체적으로, 나라 $i$에서 나라 $j$로 갈 때 $r_i > r_j + m$이면 여행자는 $t_j$일 동안 격리해야 한다.

고고학자들이 $n$개 나라 사이를 이동한 $q$명의 여행자 기록을 발견했다. 각 여행자의 출발지와 목적지는 알려져 있다. 각 여행자의 최소 이동 시간을 구하라.

첫 줄에 세 정수 $n$, $q$, $m$이 주어진다 ($2 \leq n \leq 10^5$, $1 \leq q \leq 10^5$, $0 \leq m \leq 10^9$). 각각 나라의 수, 여행자의 수, 감염률이 낮은 나라로 이동할 때 허용되는 $r$ 값 차이의 최댓값이다.

둘째 줄에는 $n$개의 정수 $r_1, \dots, r_n$이 주어진다 ($0 \leq r_1 \leq \dots \leq r_n \leq 10^9$). 각 나라의 $r$ 값이다.

셋째 줄에는 $n$개의 정수 $t_1, \dots, t_n$이 주어진다 ($0 \leq t_i \leq 10^9$). $r$ 값이 확실히 낮은 나라로 이동할 때 필요한 격리 일수이다.

다음 $q$개의 줄에는 각각 두 정수 $x$, $y$ ($1 \leq x, y \leq n$, $x \neq y$)가 주어진다. 나라 $x$에서 출발해 나라 $y$로 가는 여행자를 뜻한다.

입력 순서대로 각 여행자의 출발 나라에서 목적 나라까지 최소 이동 시간(일)을 한 줄에 하나씩 출력한다.