레이팅 미적용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?
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\).
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