The Safest Path

The rabbit Peter got the map of the city with marked pubs on it. Peter loves to go to pubs. Naturally, he would like to visit pubs at night to make it twice as interesting. Peter becomes bored if attend only one pub in night, so he often comes to several pubs.

Today, Peter decided to visit two pubs. There are roads between some pubs. It can be unsafe on dark roads, so Peter rated each road between pubs by some level of a risk: the bigger value represents the bigger risk. There can be no direct road between two particular pubs, while the path always exists via some other pubs. In this case the path safety risk is equal to the risk of most unsafe road on the path.

Peter has created a list of pub pairs which he considers to attend this night. Please help him to determine the safest path between each pair.

Input

The first line of input contains three space separated integers: n m q (1 ≤ n ≤ 100000, 1 ≤ m, q ≤ 200000) – respectively, the number of pubs, the number of roads between them and the number of pairs selected. The following m lines describe the roads; each line contains three space separated integers: a b c (0 ≤ a, b < n, 1 ≤ c ≤ 10000) – respectively, pubs, which are connected by a road, and the risk rate of the road. The last q lines describes the pairs of pubs, which, probably, be attended by peter this night; each line contains two space separated numbers: a b (0 ≤ a, b < n).

Output

Output the risk rate of the safest path between each pair of pubs in a separate line.