Trucks

A worldwide logistics company is called Loners since all of its drivers ride alone. The managers must quickly and accurately tell their clients whether a driver can deliver goods safely from city $a$ to city $b$.

The job demands responsibility and alertness. Drivers must rest at a hotel no less often than every $p$ hours. Every city has a hotel. Using the cities and the roads that connect them, write a program that answers the managers' queries.

The first line contains three integers $N$, $M$, and $U$, separated by spaces: the number of cities, the number of roads, and the number of manager queries. The cities are numbered from $1$ to $N$.

Each of the next $M$ lines contains three integers $x$, $y$, and $t$. This means it takes $t$ time to drive from city $x$ to city $y$. Roads are two-way, and the time is the same in both directions. The data always satisfies $x < y$. Two cities have at most one direct road between them.

Each of the next $U$ lines contains three integers $a$, $b$, and $p$. Here $a$ is the starting city, $b$ is the destination city, and $p$ is the maximum time the driver can drive without rest. The data always satisfies $a < b$.

For each query, print TAIP (Lithuanian for "yes") on its own line if the driver can safely deliver the goods from city $a$ to city $b$. Otherwise, print NE (Lithuanian for "no").

• $1 \le N, M, U \le 200000$
• $1 \le x, y, a, b \le N$
• $1 \le t, p \le 10^9$