Problem S
Bílstjórar

Verkefni

Flutningafyrirtæki á heimsklasa er nefnt Einverur þar sem allir bílstjórarnir keyra einsamlir. Það er mjög mikilvægt fyrir umsjónarmenn fyrirtækisins að geta svarað öllum fyrirspurnum kúnna sinna hratt og nákvæmlega um hvort bílstjórar þeirra munu geta flutt vörurnar á öruggan máta frá borg $a$ til borgar $b$.

Starf bílstjórans krefst mikillar ábyrgðar og þess að bílstjórinn sé vel vakandi. Þess vegna þurfa bílstjórar að hvíla sig á hóteli ekki sjaldnar en á $p$ klukkutíma fresti. Það eru hótel í hverri borg. Með upplýsingunum sem þú hefur um borgirnar og vegina sem tengja þær skaltu skrifa forrit sem svarar fyrirspurnum umsjónarmannanna.

Inntak

Á fyrstu línunni eru þrjár heiltölur aðskildar með bilum: $N$ - fjöldi borga, $M$ - fjöldi vega, $U$ - fjöldi fyrirspurna frá umsjónarmönnum. Borgirnar eru númeraðar frá $1$ upp í $N$.

Næst fylgja $M$ línur sem lýsa vegunum. Á hverri línu eru þrjár heiltölur aðskildar með bilum: $x$, $y$ og $t$. Þessar heiltölur lýsa að það taki $t$ tímaeiningar að keyra frá borg $x$ til borgar $y$. Keyra má þessa vegi í báðar áttir og tekur það jafn langan tíma sama í hvora átt er ferðast. Því má gera ráð fyrir að $x < y$ í gögnunum. Hverjar tvær borgir geta einungis haft einn veg á milli sín.

Að lokum fylgja $U$ línur sem tákna fyrirspurnir umsjónarmannanna. Á hverri línu eru þrjár heiltölur aðskildar með bilum: $a$ - númer borgarinnar þar sem bílstjórinn hefur ferð sína, $b$ - númer borgarinnar þar sem bílstjórinn lýkur ferð sinni, $p$ - hámarkstíminn sem bílstjórinn má keyra í án hvíldar. Gera má ráð fyrir að $a < b$.

Úttak

Fyrir hverja fyrirspurn skal forrit þitt skrifa eina línu með textanum $\texttt{TAIP}$ (já á litháensku) ef bílstjórinn getur flutt vörurnar með öruggum hætti milli borganna $a$ og $b$. Ef hann getur ekki gert það skal forrit þitt skrifa $\texttt{NE}$ (nei á litháensku) í staðinn.

Takmarkanir

• $1 \leq N, M, U \leq 200\, 000$

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

• $1 \leq t, p \leq 10^9$

Hlutverkefni

Sýnidæmi

Þó að leiðin milli borga 1 og 5 sé til ($1 \rightarrow 3 \rightarrow 5$) þá þarf að keyra í $9$ klukkustundir milli borga 1 og 3 sem er meira en hámarkstíminn sem er leyfður, sem er $6$ klukkustundir.

Það er ekki til leið milli borga 3 og 4.

Það er vegur milli borga 3 og 4. Það er hægt að ferðast milli þessarra borga með leyfða hámarkstímanum.

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

NE
NE
TAIP