High-Speed Tram Route Feasibility

The planning department of Flatland is evaluating several proposals for high-speed tram routes. Each proposal is defined by a target station and an expected travel time \(r\). However, the actual travel time may differ from the expectation. To quantify the feasibility of a route, a parameter \(p\) is used: for a route with expected time \(r\), if the actual travel time \(x\) satisfies

\[ r \le x \le \frac{p}{p-1}\times r, \]

then the route is considered feasible.

The network of Flatland's railways is given as a directed graph with weighted edges representing travel times. The tram always starts from station 1. For each proposed route (defined by a target station and expected time), determine whether there exists a simple path (i.e. no repeated stations) starting at station 1 and ending at the target station such that the total travel time \(x\) satisfies the condition above.

inputFormat

The input is given as follows:

1. The first line contains three integers \(n\), \(m\), and \(p\) where \(n\) is the number of stations, \(m\) is the number of railway segments, and \(p (>1)\) is the parameter for feasibility evaluation.
2. The next \(m\) lines each contain three integers \(u\), \(v\), and \(t\), indicating that there is a directed edge (rail segment) from station \(u\) to station \(v\) with travel time \(t\).
3. The next line contains an integer \(q\), the number of route proposals.
4. Each of the following \(q\) lines contains two integers: target and \(r\), where target is the destination station and \(r\) is the expected travel time.

You may assume that all numbers are positive integers and that station 1 is the starting station.

outputFormat

For each of the \(q\) proposals, output a single line containing YES if there exists a simple path from station 1 to the target station whose total travel time \(x\) satisfies

[ r \le x \le \frac{p}{p-1} \times r, ]

and NO otherwise.

sample

4 4 2
1 2 2
2 3 3
1 3 5
3 4 2
2
3 5
4 7

YES
YES