Laiko ribojimas: 2s

Atminties ribojimas: 512MB

Duomenų failas: lmio_2017_sunkvezimiai_vyr.in

Rezultatų failas: lmio_2017_sunkvezimiai_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Sunkvežimiai (LMIO 2017)

Visoje Europoje dirbančios logistikos įmonės „Vienišiai“ (įmonė taip vadinasi, nes visi vairuotojai važinėja po vieną) vadybininkams labai svarbu greitai ir tiksliai atsakyti užsakovams, ar vairuotojai galės saugiai pervežti krovinį iš miesto a į miestą b.

Vairuotojų darbas yra atsakingas ir reikalauja budrumo, todėl jie privalo ne rečiau nei kas p valandų pailsėti viešbutyje, kurių yra kiekviename mieste. Turėdami informaciją apie miestus ir juos jungiančius kelius, parašykite programą atsakysiančią į vadybininkų užklausas.

Pradiniai duomenys

Pirmoje eilutėje pateikti trys tarpais atskirti sveikieji skaičiai: N - miestų skaičius, M - kelių skaičius, U - vadybininko pateiktų užklausų skaičius. Miestai numeruojami nuo 1 iki N.

Tolesnėse M eilučių pateikta informacija apie kelius. Kiekvienoje eilutėje įrašyti trys tarpais atskirti sveikieji skaičiai: x, y ir t, kurie nusako, kad nuvažiuoti tarp miestų x ir y užtrunka t laiko. Keliai visada yra dvipusiai ir jais važiuoti abiem kryptimis užtrunka vienodai, todėl patogumo dėlei galios sąlyga x<y. Tarp dviejų miestų gali būti tik vienas tiesioginis kelias.

Paskutinėse U eilučių pateikiamos vadybininkų užklausos. Kiekvienoje iš U eilučių pateikiami trys sveikieji skaičiai: a -- pradžios miesto numeris, b -- pabaigos miesto numeris, p -- laikas, kiek ilgiausiai vairuotojas gali važiuoti be poilsio. Galios sąlyga a<b.

Išvestis

Jūsų programa turi kiekvienai užklausai atskiroje eilutėje išvesti TAIP, jeigu vairuotojas gali saugiai pristatyti krovinį tarp miestų a ir b, arba NE, jeigu negali.

Ribojimai

Visiems testams galios ribojimai 1\\leqN,M,U\\leq200\\,000, 1\\leqx,y,a,b\\leqN, 1\\let,p\\le10^9.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 3 3
1 3 9
2 4 2
3 5 8
1 5 6
3 4 100
2 4 3
 
NE
NE
TAIP