Problem E
Förare

Uppgift

Efter att Joshua föreläste om strategier och debugging (och berättade för sina fina deltagare flertals omoraliska förslag för att bli bra på programmering) har Joshua lyckats starta ett omänskligt logistikföretag vid namnet Loners. Joshuas idé med företaget är att alla förare måste åka helt ensamma utan någon form av kommunikation eller interaktion, för den enkla anledningen att förarna kommer kunna fokusera på att förbättra sitt körande och kommer på nolltid bli Formula 1 vinnare. Utöver det är det mycket viktigt för Joshua att kunna svara sina klienter snabbt och korrekt på om förarna kommer att leverera sina varor säkert från stad $a$ till stad $b$. Förarens arbete kräver ansvar och vaksamhet. Av den anledningen krävs det att de vilar på ett hotell inte mer sällan än varje $p$ timmar. Det finns hotell i varje stad. Med den information du har om städer och vägar som förbinder dem, skriv ett program som skulle svara på förfrågningar som Joshua får.

Indata

På första raden presenteras tre heltal åtskilda av mellanslag: $N$ - antal städer, $M$ - antal vägar, $U$ - antal förfrågningar som Joshua behöver svara på. Städerna är numrerade från $1$ till $N$.

På de följande $M$ raderna finns information om vägarna presenterade. På varje rad finns tre heltal åtskilda av mellanslag: $x$, $y$ och $t$. Dessa heltal beskriver att det tar $t$ tid att köra från stad $x$ till stad $y$. Vägarna är alltid tvåvägs och det tar alltid samma tid att köra åt båda hållen. Därför är villkoret $x < y$ alltid giltigt i dessa data. De två städerna kan bara ha en direkt väg mellan dem.

På de återstående $U$ raderna presenteras Joshuas förfrågningar. På var och en av de $U$ raderna presenteras tre heltal: $a$ - numret på den ursprungliga staden, $b$ - numret på slutstaden, $p$ - maximal tid som föraren kan köra utan vila. Villkoret $a < b$ kommer att vara giltigt.

Utdata

För varje förfrågan ska ditt program skriva ut $\texttt{TAIP}$ (litauiska för ja) på en separat rad om föraren säkert kan leverera varorna mellan städerna $a$ och $b$. Om han inte kan göra det ska programmet skriva ut $\texttt{NE}$ (litauiska för nej).

Gränser

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

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

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

Delpoäng

Exempel

Även om vägen mellan städerna 1-5 existerar ($1 \rightarrow 3 \rightarrow 5$), det krävs att köra i $9$ timmar mellan städerna 1-3, dvs. mer än den maximala tiden på $6$ timmar.

Vägen mellan 3-4 existerar inte.

Det finns en direkt väg mellan städerna 2-4. Det är möjligt att resa mellan dessa städer inom den tillåtna tiden.

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

NE
NE
TAIP