Sacensībās RatingCode piedalās n lietotāji, kur k-tajam lietotājam piešķirts reitings ar vērtību a_k. Vienā sacensību reizē katra lietotāja reitings var vai nu palielināties, vai nu samazināties par veselu pozitīvu skaitli d. Lietotājiem interesē jautājumi veidā: kāds ir mazākais nepieciešamais sacensību reižu skaits, lai no sākotnējā stāvokļa i-tajam lietotājam reitings kļūtu j-tais lielākais un nebūtu vienāds ar neviena cita lietotāja reitingu? Ievērojiet, ka reitings var kļūt arī negatīvs skaitlis.

Pirmajā rindā doti divi veseli pozitīvi skaitļi n un d, lietotāju skaits un reitinga izmaiņas vērtība vienā sacensību reizē (1 ≤ n ≤ 10⁶, 1 ≤ d ≤ 10⁹).
Otrajā rindā doti n veseli pozitīvi skaitļi a₁, a₂, ..., a_n, lietotāju reitingu vērtības (10⁹ ≥ a_1 > a_2 > ... > a_n ≥ 1).
Trešajā rindā dots viens skaitlis q, jautājumu skaits (1 ≤ q ≤ 10⁶).
Katrā no nākošajām q rindām dots pa diviem skaitļiem i un j, lietotāja sākotnējā vieta, un prasītā vieta (1 ≤ i, j ≤ n, i ≠ j).

Jāizvada rinda no q skaitļiem, atdalītiem ar tukšumzīmēm, kas ir atbildes uz jautājumiem tādā secībā, kādā tie uzdoti ievadā.

Punkti par testiem:

1. 20% - a₁ ≤ 100.
2. 30% - a₁ ≤ 5000.
3. 50% - uzdevumā dotie ierobežojumi.

Autors: Jevgēnijs Vihrovs.