Magical Road Incantations

In a magical kingdom, there are (n) cities connected by (m) undirected roads, each with an associated magical weight. You have (k) incantations at your disposal. In each incantation, you must select the road with the highest weight and reduce its weight by half (using integer division). After performing up to (k) incantations, compute the shortest path cost between pairs of cities as given in the queries.

More formally, each road between cities (u) and (v) initially has weight (w). For each incantation, identify the road with maximum weight (if there are multiple, choose any) and update its weight to (\lfloor w/2 \rfloor). Afterwards, the shortest path cost between any two cities is defined as the minimum total weight among all possible paths between them. Your task is to answer several queries where each query asks for the shortest path cost between two specified cities after all incantations have been applied.

inputFormat

The first line contains three integers (n), (m), and (k) representing the number of cities, the number of roads, and the number of incantations respectively. Each of the next (m) lines contains three integers (u), (v), and (w) denoting a road between cities (u) and (v) with weight (w). The next line contains an integer (q), the number of queries. Finally, each of the next (q) lines contains two integers (a) and (b), representing a query for the shortest path cost between city (a) and city (b).

outputFormat

For each query, output a single integer on a new line representing the minimum possible path cost between the two cities after applying the incantations.## sample

5 10 5
1 2 10
1 3 20
1 4 15
1 5 30
2 3 25
2 4 30
2 5 10
3 4 35
3 5 40
4 5 25
3
1 5
2 4
3 5

15
15
20