I. International Irregularities
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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 \gt 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.

Examples
Input
5 4 1
0 5 6 7 8
3 4 1 5 10
1 4
4 1
4 2
5 2
Output
1
4
2
3
Input
5 4 10
0 8 20 25 30
5 11 13 6 3
5 1
5 2
5 3
5 4
Output
6
7
1
1