International Irregularities

Long ago on a planet far, far away, a highly contagious virus caused a long-lasting pandemic.

Even so, people still wanted to travel between countries for their summer holidays. Before the pandemic, travel from any country to any other country took 1 full day. During the pandemic, however, some countries did not want travellers from areas with higher infection rates. They required those travellers to quarantine for a set number of days before they could continue their trip or start their holiday.

To keep things fair, an independent Bureau for Accurate Pandemic Classification assigned an $r$-value to each country based on its infection rate. A higher $r$-value means a higher infection rate.

Each country asks tourists to quarantine when the country they just came from has an $r$-value well above its own. Specifically, when travelling from country $i$ to country $j$, the tourist must quarantine for $t_j$ days if $r_i > r_j + m$.

Archaeologists found evidence of $q$ tourists travelling between $n$ countries. The start and destination of each tourist are known. Find the minimal travel time for each tourist.

The first line contains three integers $n$, $q$, and $m$ ($2 \leq n \leq 10^5$, $1 \leq q \leq 10^5$, $0 \leq m \leq 10^9$), the number of countries, the number of tourists, and the maximum allowed difference between two $r$-values when travelling to a country with a lower infection rate.

The second line contains $n$ integers $r_1, \dots, r_n$ ($0 \leq r_1 \leq \dots \leq r_n \leq 10^9$), the $r$-value of each country.

The third line contains $n$ integers $t_1, \dots, t_n$ ($0 \leq t_i \leq 10^9$), the quarantine time in days required when travelling to a country with a significantly lower $r$-value.

The next $q$ lines each contain two integers $x$ and $y$ ($1 \leq x, y \leq n$, $x \neq y$), meaning a tourist departs from country $x$ with destination $y$.

For each tourist, in the order they appear in the input, print the minimal travel time in days from the departure country to the destination country, one per line.