C. Cactus Simple Path Queries
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a connected, undirected, simple cactus graph. A cactus graph is a connected graph in which every edge belongs to at most one simple cycle. Equivalently, any two simple cycles have at most one common vertex.

Each edge has an integer weight, and weights may be negative.

Then you have to answer $$$q$$$ queries. In each query, two vertices $$$u$$$ and $$$v$$$ are given, and you must find the minimum possible total weight of a simple path from $$$u$$$ to $$$v$$$.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \le n \le 200'000$$$, $$$n - 1 \le m \le 300'000$$$, $$$1 \le q \le 200'000$$$).

Each of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$, $$$-10^9 \le w_i \le 10^9$$$), meaning that there is an undirected edge between $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$.

It is guaranteed that the graph is simple, connected, and is a cactus.

Each of the next $$$q$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), describing one query.

Output

For each query, print one integer: the minimum possible total weight of a simple path from $$$u$$$ to $$$v$$$.

Example
Input
5 5 3
1 2 5
2 3 -10
3 4 5
4 1 1
3 5 2
1 3
5 4
2 4
Output
-5
-2
-5
Note

There are two simple paths from $$$1$$$ to $$$3$$$:

  • $$$1 \rightarrow 2 \rightarrow 3$$$, with total weight $$$5 + (-10) = -5$$$;
  • $$$1 \rightarrow 4 \rightarrow 3$$$, with total weight $$$1 + 5 = 6$$$.

So the answer to the first query is $$$-5$$$.