Fişierul intrare/ieşire:	avioane2.in, avioane2.out	Sursă	ONIS 2016 Runda Online
Autor	Eugenie Daniel Posdarascu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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.

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).

Date de ieşire

Fişierul de ieşire avione.out va contine K linii, rasunsul pentru fiecare query. Daca nu se poate ajunge intr-un anumit pana la un anumit timp dat, afisati -1.

Restricţii

• 1 ≤ N ≤ 30.000
• 1 ≤ M ≤ 90.000
• 1 ≤ K ≤ 120.000
• Toate celalalte valori fac parte din intervalul [1, 10⁹]
• Mihai si Alexandra trebuie sa plateasca un singur bilet pentru fiecare zbor.
• Personajele pot astepta oricat intr-un aeroport (la o cafea) urmatorul zbor.
• T_dec < T_Ater pentru fiecare din cele M zboruri

Exemplu

Cum se trimit solutii?