Problem S
Vairuotojai

Užduotis

Tarptautinė pervežimų kompanija vadinasi "Vienišiai", nes visi vairuotojai dirba po vieną. Vadovams labai svarbu klientams greitai ir tiksliai atsakyti, ar vairuotojai galės pervežti jų prekes iš miesto $a$ į miestą $b$.

Vairuotojų darbas reikalauja atsakomybės ir budrumo, dėl to jie privalo pailsėti viešbutyje ne rečiau nei kas $p$ valandų. Kiekviename mieste yra viešbučių. Naudodamiesi informacija apie miestus ir juos jungiančius kelius, parašykite programą, kuri atsakytų į vadovų užklausas.

Pradiniai duomenys

Pirmojoje eilutėje yra trys sveikieji skaičiai: $N$ - miestų skaičius, $M$ - kelių skaičius, $U$ - vadovų užklausų skaičius. Miestai yra sunumeruoti nuo $1$ iki $N$.

Kitose $M$ eilučių yra pateikta informacija apie kelius. Kiekvienoje eilutėje yra trys sveikieji skaičiai: $x$, $y$ ir $t$. Šie skaičiai reiškia, kad užtrunka $t$ valandų nuvažiuoti iš miesto $x$ į miestą $y$. Visi keliai yra dvipusiai ir keliauti abiem kryptimis užtrunka tiek pat laiko, todėl visada $x<y$. Tarp dviejų miestų yra tik vienas tiesioginis kelias.

Kitose $U$ eilučių yra pateiktos vadovų užklausos. Kiekvieną užklausą aprašo trys sveikieji skaičiai: $a$ - pradinio miesto numeris, $b$ - galutinio miesto numeris, $p$ - ilgiausias laikas, kiek vairuotojas gali važiuoti be poilsio. Visada galioją sąlyga: $a<b$.

Rezultatai

Programa atsakymus į užklausas turi išvesti skirtingose eilutėse. Jūsų programa turi išvesti $\mathtt{\text{TAIP}}$, jei vairuotojas gali saugiai pervežti krovinį tarp miestų $a$ ir $b$. Jei to padaryti negalima, programa turi išvesti $\mathtt{\text{NE}}$.

Ribojimai

• $1\le N,M,U\le 200000$

• $1\le x,y,a,b\le N$

• $1\le t,p\le {10}^9$

Dalinės užduotys

Pavyzdžiai

Nors kelias tarp miestų 1–5 egzistuoja ($1\to 3\to 5$), tarp miestų 1–3 reikia važiuoti 9 valandas, t.y., ilgiau nei daugiausiai leidžiama (6 valandas).

Kelio tarp miestų 3–4 nėra.

Yra tiesioginis kelias tarp miestų 2–4. Tarp šių miestų galima nuvažiuoti nepažeidžiant maksimalaus darbo valandų kiekio.

5 3 3
1 3 9
2 4 2
3 5 8
1 5 6
3 4 100
2 4 3

NE
NE
TAIP