30497번 - 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 $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.

제한

힌트