Avioane2

avioane2

== include(page="template/taskheader" task_id="avioane2") ==

Mihai si Alexandra s-au decis sa mearga in vacanta in strainatate. Problema lui Mihai este ca mereu Alexandra trebuie sa decida daca are rost sa mearga intr-o anumita excursie sau nu (in functie de bani, timp, etc.).
 
Fie $N$ aeroporturi (reprezentate ca nodurile unui graf) si $M$ zboruri (muchiile grafului). Pentru fiecare zbor se cunoaste indicele aeroportului si timpul la care decoleaza avionul, indicele aeroportului si timpul la care aterizeaza avionul si pretul biletului pentru acest zbor. Mihai si Alexandra se afla in aeroportul $1$ la timpul $0$. Mihai trebuie sa raspunda la $K$ query-uri de tipul $(x,y):$ care este pretul minim pentru a ajunge in aeroportul $x$ la timpul maxim $y$.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $avioane2.in$ va contine pe prima linie $3$ numere naturale $N$, $M$ si $K$. Pe urmatoarele $M$ linii se afla cate $5$ valori reprezentand detaliile unui zbor: $A$, $T{~dec~}$, $B$, $T{~Ater~}$ (avionul pleaca din $A$ la timpul $T{~dec~}$ si ajunge in B la timpul $T{~Ater~}$) si $P$, pretul biletului. Urmatoarele $K$ linii contin cate $2$ numere naturale reprezentand query-urile de tipul $(x,y)$.

Fişierul de intrare $avioane2.in$ ...

h2. Date de ieşire

Fişierul de ieşire $avione.out$ va contine $K$ linii, rasunsul pentru fiecare query.

În fişierul de ieşire $avioane2.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 300.000$
* $1 ≤ K ≤ 200.000$
* Toate celalalte valori fac parte din intervalul $[1, 10^9^]$
* Mihai si Alexandra trebuie sa plateasca un singur bilet pentru fiecare zbor.
* Personajele pot astepta oricat intr-un aeroport (la o cafea) urmatorul zbor.

* $... ≤ ... ≤ ...$

h2. Exemplu