Delivery Driver's Break Optimization

A delivery driver must complete various delivery tasks in a city represented by intersections and one-way streets. Each street has an associated distance, and the driver can travel up to a distance D per hour without a break. Between intersections, if the total distance exceeds multiples of D, the driver must take a break. Given a city map and a series of delivery queries, compute for each query the minimum number of breaks required.

Formally, let the city have N intersections and M directed roads. Each road is described by a triple \( (A_i, B_i, C_i) \) meaning there is a road from intersection \( A_i \) to \( B_i \) with distance \( C_i \). For each query \( (s, t) \), determine the shortest distance from s to t using the available roads, and if that shortest distance is \( L \), then the number of breaks required is \( \left\lfloor \frac{L-1}{D} \right\rfloor \). If there is no path from s to t, output -1.

Note: All formulas are in LaTeX format. The answer should process input from stdin and output to stdout.

inputFormat

The first line contains three integers N, M, and D, where N is the number of intersections, M is the number of one-way streets, and D is the maximum distance the driver can cover in one hour without taking a break.

The next M lines each contain three integers u, v, and w representing a one-way street from intersection u to v with distance w.

The following line contains an integer Q, the number of delivery queries.

Each of the next Q lines contains two integers s and t representing a delivery task from intersection s to intersection t.

Input is provided via stdin.

outputFormat

Output Q lines. Each line contains a single integer representing the minimum number of breaks needed for the corresponding delivery query. If a destination is unreachable, output -1.

Output is printed to stdout.

## sample

4 4 5
1 2 3
2 3 4
3 4 6
1 3 2
2
1 4
3 1

1
-1

</p>