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 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. Deoarece orasul este unul in curs de dezvoltare, este deocamdata plin de gropi. Danut stie dinainte harta orasului: stie 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 pastreaza viteza constanta la 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), 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₂), 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

Exemplu

Explicatie

Orasul arata astfel:

Cum se trimit solutii?