Country-wide Highway Infrastructure Planning

You are given a country with n major cities and m possible highway connections. Each highway has an associated cost. Two government committees impose the following constraints on any highway to be built: its cost must be at least \(l\) and at most \(h\). Your goal is to select a set of highways (each satisfying \(l \le c \le h\)) such that the resulting network connects as many pairs of cities (possibly indirectly) as possible. In other words, you must maximize the total number of connected city pairs.

Note that if the network is disconnected, the total number of connected pairs is the sum of \(\binom{k}{2}\)'s over each connected component (where \(k\) is the number of cities in that component). Among all networks achieving this maximum connectivity, you are to choose one with the minimum total cost. Since any cycle in a connected component is redundant, the problem reduces to finding a minimum spanning forest in the graph formed by highways with costs in the interval \([l, h]\). Your task is to compute the total cost of this minimum spanning forest.

Input Note: Due to political meddling, you will have to answer several queries, each providing new values for \(l\) and \(h\).

inputFormat

The input begins with a line containing three integers: \(n\) \(m\) \(q\) — the number of cities, the number of available highway connections, and the number of queries, respectively.

Then follow \(m\) lines. Each of these lines contains three integers \(u\), \(v\), and \(c\), representing a highway connecting city \(u\) and city \(v\) with cost \(c\). It is guaranteed that the cities are numbered from 1 to \(n\).

Then follow \(q\) lines. Each query is given as two integers \(l\) and \(h\), the inclusive lower and upper bounds on the cost of highways allowed for that query.

outputFormat

For each query, output a single line containing one integer: the total cost of the minimum spanning forest that connects the maximum number of city pairs using only highways with cost in the interval \([l, h]\).

sample

4 5 1
1 2 4
2 3 7
3 4 6
1 4 10
1 3 8
5 9

21