Fişierul intrare/ieşire:	gropi.in, gropi.out	Sursă	Junior Challenge 2008
Autor	Filip Cristian Buruiana	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.225 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Gropi

Datorita rezultatelor foarte bune pe care le obtinuse la Olimpiada Balcanica pentru Juniori in urma cu 5 ani, Danut primeste la majorat de la parintii sai o masina noua (nu de jucarie). Pentru ca e doritor sa o testeze, el hotaraste sa faca diferite trasee prin oras. Orasul lui Danut poate fi considerat, pentru simplitate, o matrice cu 2 linii si C coloane, in care fiecare zona a orasului corespunde unei casute din matrice. O astfel de zona este identificata prin coordonatele sale: numarul liniei si numarul coloanei pe care se afla. Deoarece orasul este unul in curs de dezvoltare, este deocamdata plin de gropi. Danut stie dinainte care dintre zonele din oras sunt bune, si care sunt pline de gropi. El nu vrea sa isi strice masina si de aceea nu va trece niciodata printr-o zona cu gropi. Danut are de gand sa faca M trasee intre zone cunoscute din oras si se intreaba, pentru fiecare din aceste M trasee pe care le planuieste, care este timpul minim in care poate fi parcurs, astfel incat zonele cu gropi sa fie ocolite. Se stie ca durata de deplasare printr-o zona fara gropi a orasului dureaza exact 1 minut (Danut merge cu o viteza constanta de 50 km/h).

Date de intrare

Fisierul de intrare gropi.in contine pe prima linie doua numere naturale, C, care reprezinta numarul de coloane din reprezentarea schematica a orasului, si N, numarul de zone din oras care au gropi si trebuie ocolite. Pe fiecare din urmatoarele N linii se gaseste cate o pereche de numere naturale (x y), 1 ≤ x ≤ 2, 1 ≤ y ≤ C, care reprezinta coordonatele unei zone cu gropi. Urmatoarea linie contine numarul M, numarul de trasee pe care le efectueaza Danut. Fisierul contine apoi M linii, pe fiecare aflandu-se cate patru numere naturale, (x₁ y₁ x₂ y₂), 1 ≤ x1, x2 ≤ 2, 1 ≤ y1, y2 ≤ C, cu semnificatia ca Danut doreste sa plece cu masina de la zona de coordonate (x₁ y₁) si sa ajunga la zona de coordonate (x₂ y₂).

Date de iesire

In fisierul de iesire gropi.out se vor afla exact M numere naturale. FIecare linie contine durata minima a traseului corespunzator din fisierul de intrare.

Restrictii

• 1 ≤ N ≤ minim(100 000, 2*C)
• 1 ≤ M ≤ 100 000
• 2 ≤ C ≤ 2 000 000 000
• Pentru 50% din teste, C ≤ 250 si M ≤ 200
• Cele N zone care contin gropi sunt distincte doua cate doua
• Se garanteaza ca se poate ajunge din orice zona in oricare alta fara a trece prin zone cu gropi
• Punctele de plecare si sosire pentru fiecare traseu nu sunt zone cu gropi

Exemplu

Explicatie

Pentru primul traseu din cele doua, o posibila solutie este cea din desenul de mai jos. Zonele negre sunt cele care contin gropi si nu pot fi parcurse cu masina. Pentru ca sunt parcurse 8 zone (8 patratele), traseul dureaza in total 8 minute.

Cum se trimit solutii?