h2. 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$.

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

h2. Restricţii

* $1 ≤ N ≤ 30.000$
* $1 ≤ M ≤ 90.000$
* $1 ≤ K ≤ 120.000$

* $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.

* $T{~dec~} < T{~Ater~}$ pentru fiecare din cele $M$ zboruri

h2. Exemplu
table(example). |_. avioane2.in |_. avioane2.out |

|5 7 6
1 4 5 8 69
2 14 3 17 25
4 2 5 10 564
5 8 2 13 12
3 20 1 25 54
2 4 4 7 34
1 1 3 8 1000
3 10
3 20
5 7
2 20
1 100
5 13
|1000
106
-1
81
0
69

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

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