International Irregularities

문제

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 $rr$-value to each country based on the infection rate in that country. A higher $rr$-value indicates higher infection rate.

Each country asked tourists to quarantine if the country they just came from had a $rr$-value significantly higher than their own. In particular, when you wanted to travel from country $ii$ to country $jj$, you would have to quarantine for $t_{j}t\_j$ days if $r_i>r_j+mr\_i\; >\; r\_j\; +\; m$.

Archaeologists have found evidence of $qq$ tourists travelling between $nn$ 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?

입력

The input consists of:

• One line with three integers $nn$, $qq$, and $mm$ ($2\le n\le {10}^{5}2\backslash leq\; n\; \backslash leq\; 10^5$, $1\le q\le {10}^{5}1\backslash leq\; q\; \backslash leq\; 10^5$, $0\le m\le {10}^{9}0\backslash leq\; m\; \backslash leq\; 10^9$), the number of countries, the number of tourists, and the maximum allowed difference between two $rr$-values when travelling to a country with a lower infection rate.
• One line with $nn$ integers $r_1,\dots ,r_{n}r\_1,\; \backslash dots,\; r\_n$ ($0\le r_1\le \cdots \le r_n\le {10}^{9}0\; \backslash leq\; r\_1\; \backslash leq\; \backslash dots\; \backslash leq\; r\_n\; \backslash leq\; 10^9$), the $rr$-value for each country.
• One line with $nn$ integers $t_1,\dots ,t_{n}t\_1,\; \backslash dots,\; t\_n$ ($0\le t_i\le {10}^{9}0\; \backslash leq\; t\_i\; \backslash leq\; 10^9$ for all $ii$), the required quarantine time in days when travelling to a country with a significantly lower $rr$-value.
• $qq$ lines, each with two integers $xx$ and $yy$ ($1\le x,y\le n1\; \backslash leq\; x,\; y\; \backslash leq\; n$, $x\mathrm{\ne }yx\; \backslash neq\; y$), indicating a tourist departing from country $xx$ with final destination $yy$.

출력

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