== include(page="template/taskheader" task_id="gropi") ==
Poveste si cerinta...
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).
h2. Date de intrare
Fisierul de intrare $gropi.in$ ...
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{~1~} y{~1~} x{~2~} y{~2~})$}, {$1 ≤ x1, x2 ≤ 2, 1 ≤ y1, y2 ≤ C$}, cu semnificatia ca Danut doreste sa plece cu masina de la zona de coordonate {$(x{~1~} y{~1~})$} si sa ajunga la zona de coordonate {$(x{~2~} y{~2~})$}.
h2. Date de iesire
In fisierul de iesire $gropi.out$ ...
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.
h2. 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
h2. Exemplu
table(example). |_. gropi.in |_. gropi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|10 4
1 3
2 9
1 7
1 5
3
1 1 1 6
1 9 2 1
1 1 1 10
|8
10
12
|
h3. 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.
!problema/gropi?oras.jpg!
== include(page="template/taskfooter" task_id="gropi") ==
