Ride a Car#520

Ride a Car

... Due to new regulations, drivers are required to have batteries ...

You have a connected weighted undirected graph with vertices and edges. You also have a car with a fuel tank that holds at most liters.

When you are at a vertex, you may optionally refuel, which fills the tank back to exactly liters. To traverse an edge of weight , you must have at least liters of fuel in the tank; doing so costs exactly liters.

You are given queries. For each query : what is the minimum number of refuels needed to travel from to , starting with a full tank? If it is impossible, print -1.

Input

The first line contains three integers , , and (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 1 \le V \le 10^9) — the number of vertices, the number of queries, and the fuel tank capacity.

The following lines each contain three integers u_i, v_i, c_i (1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le c_i \le 10^9) — an edge between u_i and v_i with weight c_i.

It is guaranteed that the graph is connected and contains no self-loops.

The following lines each contain two integers s_i and t_i (1 \le s_i, t_i \le n, s_i \neq t_i) — the -th query.

Output

Print lines. The -th line should contain a single integer — the minimum number of refuels for the -th query, or if it is impossible.

Examples

Example 1

Loading
Loading

Note

The graph has vertices, edges, and the fuel tank capacity is V = 4.

  1. Query 6 \to 7: travel 6 \to 4 \to 3 \to 5 (using 1 + 2 + 1 = 4 liters, tank empty), refuel at vertex , then 5 \to 7 (using liters). Minimum refuels: .

  2. Query 7 \to 6: travel 7 \to 5 (using liters, tank empty), refuel at vertex , then 5 \to 3 \to 4 \to 6 (using 1 + 2 + 1 = 4 liters). Minimum refuels: .

  3. Query 3 \to 2: travel directly 3 \to 2 using the edge of weight  (tank goes from to ). No refuel needed. Minimum refuels: .

Scoring

  1. ( points) n \le 3, q \le 10;

  2. ( points) n \le 300, q \le 300;

  3. ( points) n \le 5000, q \le 5000;

  4. ( points) V = 1, there exists only one path from s_i to t_i;

  5. ( points) V = 1;

  6. ( points) there exists only one path from s_i to t_i;

  7. ( points) n \le 10^5, q \le 10^5;

  8. ( points) no additional restrictions.