Problem I
International Irregularities

Generated using canva.com with prompt “Traveller with backpack and facemask, in front of mountains”.

Long, long ago on a planet far, far away, a highly contagious virus caused an enduring pandemic.

Even so, the people wanted to travel between countries for their summer holidays. In the good old before-days, travelling from any country to any other country took 1 full day. However, during the pandemic, certain countries preferred not to receive travellers from areas that had higher infection rates, so they made them quarantine for a certain number of days before allowing them to continue their trip or start their holiday.

To keep everything fair, an independent Bureau for Accurate Pandemic Classification was founded. They assigned a $r$-value to each country based on the infection rate in that country. A higher $r$-value indicates higher infection rate.

Each country asked tourists to quarantine if the country they just came from had a $r$-value significantly higher than their own. In particular, when you wanted to travel from country $i$ to country $j$, you would have to quarantine for $t_j$ days if $r_i > r_j + m$.

Archaeologists have found evidence of $q$ tourists travelling between $n$ countries. For each tourist, the start and destination are known. The question that remains to be answered is: how long was each tourist’s minimal travel time?

Input

The input consists of:

• One line with 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.

• One line with $n$ integers $r_1, \dots , r_n$ ($0 \leq r_1 \leq \dots \leq r_n \leq 10^9$), the $r$-value for each country.

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

• $q$ lines, each with two integers $x$ and $y$ ($1 \leq x, y \leq n$, $x \neq y$), indicating a tourist departing from country $x$ with final destination $y$.

Output

For each tourist, output their minimal travel time in days between their departure country and destination country, in the order in which they appear in the input.

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

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