Max Interest Trip

In this problem, you are given an undirected, weighted graph representing a network of cities. Each city has an attraction point with a given interest value. You are then provided with a number of trips, where each trip specifies a starting city and a destination city. Your task is to find the maximum interest value among all the cities lying on the shortest path between the given cities (including both the starting and the destination cities).

Formally, for a trip from city (s) to city (t), let (P(s,t)) denote the set of cities on the shortest path and let (I_i) be the interest value of city (i). The answer for the trip is:

(\max_{i \in P(s,t)} I_i)

If there are several shortest paths, consider the one that gives the maximum interest value.

inputFormat

The input is read from standard input and is formatted as follows:

The first line contains three integers (n), (r), and (m), where (n) is the number of cities, (r) is the number of roads, and (m) is the number of trips.

The second line contains (n) integers, where the (i)th integer represents the interest value of city (i).

Then (r) lines follow, each containing three integers (u), (v), and (w), indicating that there is an undirected road between cities (u) and (v) with distance (w).

Finally, there are (m) lines, each containing two integers (s) and (t), representing a trip from city (s) to city (t).

outputFormat

For each trip, output a single line with one integer: the maximum interest value among all cities on the shortest path from city (s) to city (t).## sample

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

8
8
8