Kādā pilsētā visas ielas ir vienvirziena un katra no tām ir vērsta vai nu ziemeļu (kartē vertikāli uz augšu), vai dienvidu (kartē vertikāli uz leju), vai rietumu (kartē horizontāli pa kreisi), vai austrumu (kartē horizontāli pa labi) virzienā (skat. 1. attēlu).

Kopumā $N$ ielas ir vērstas ziemeļu vai dienvidu virzienā, bet $M$ ielas — austrumu vai rietumu virzienā. Ziemeļu/dienvidu ielas ir sanumurētas ar naturāliem skaitļiem no $1$ līdz $N$ pēc kārtas, sākot no kreisās puses uz labo, bet rietumu/austrumu ielas ir sanumurētas ar naturāliem skaitļiem no $1$ līdz $M$ pēc kārtas, sākot no augšas uz leju.

Ielu tīkla piemērs, kur $N=7$ un $M=8$, parādīts 2. attēlā.

Katru krustojumu varam viennozīmīgi raksturot, norādot ziemeļu/dienvidu un rietumu/austrumu ielu numurus.

Par ielas posmu sauksim ielas nogriezni starp diviem krustojumiem (posmā var būt citi krustojumi), kas vērsts attiecīgās ielas virzienā. Piemēram, $(3; 8) \to (1; 8)$ ir posms, bet $(4; 5) \to (2; 5)$ — nav. Nepieciešams noteikt, kāds mazākais ielu posmu skaits jāveic, lai no viena krustojuma tiktu līdz kādam citam, ja tas vispār ir iespējams.

Piemēram, 2. attēlā, lai no krustojuma $(1; 8)$ nonāktu krustojumā $(7; 1)$, jāveic divi posmi: $(1; 8) \to (1; 1) \to (7; 1)$. Lai no $(6; 8)$ nokļūtu $(4; 4)$, vajadzēs izmantot, mazākais, trīs posmus: $(6; 8) \to (3; 8) \to (3; 4) \to (4; 4)$ vai $(6; 8) \to (6; 2) \to (4; 2) \to (4; 4)$, vai vēl kādā citā veidā. Savukārt, viegli pamanīt, ka no neviena cita krustojuma nav iespējams nonākt krustojumā $(7; 8)$, jo abas ielas "iet prom" no šī krustojuma.

Uzrakstiet datorprogrammu, kas dotam ceļu tīklam katram no dotajiem krustojumu pāriem nosaka, ar kādu mazāko posmu skaitu no pirmā krustojuma iespējams tikt uz otro, ja tas ir iespējams!

Pirmajā rindā doti naturāli skaitļi $N$ (ielu skaits ziemeļu/dienvidu virzienā, $N \leq 10^5$), $M$ (ielu skaits rietumu/austrumu virzienā, $M \leq 10^5$) un $P$ (krustojumu pāru skaits, $P \leq 10^5$).

Otrajā rindā kā pirmais dots vesels nenegatīvs skaitlis $D$ (ielu skaits dienvidu virzienā, $0 \leq D \leq N$). Tam seko $D$ naturāli skaitļi augošā secībā: ielu, kas vērstas dienvidu virzienā, numuri. Pārējās $N - D$ ielas ir vērstas ziemeļu virzienā.

Trešajā rindā kā pirmais dots vesels nenegatīvs skaitlis $A$ (ielu skaits austrumu virzienā, $0 \leq A \leq M$). Tam seko $A$ naturāli skaitļi augošā secībā: ielu, kas vērstas austrumu virzienā, numuri. Pārējās $M - A$ ielas ir vērstas rietumu virzienā.

Nākamajās $P$ rindās katrā ir viena krustojumu pāra apraksts — četri naturāli skaitļi $x_1$, $y_1$, $x_2$, $y_2$ ($x_1 \leq N$, $y_1 \leq M$, $x_2 \leq N$, $y_2 \leq M$), kur $(x_1; y_1)$ ir pirmā krustojuma, bet $(x_2; y_2)$ — otrā krustojuma koordinātas.

Izvaddatiem jāsatur tieši $P$ rindas. Katram $i$ ($1 \leq i \leq P$) izvaddatu $i$-tajā rindā jābūt atbildei par krustojumu pāri, kas ievaddatos dots kā $i$-tais pēc kārtas. Ja no pirmā krustojuma iespējams nonākt otrajā, tad atbildei jābūt mazākajam ielu posmu skaitam, kas to ļauj paveikt, vai, ja nokļūt nav iespējams, skaitlim $-1$.