Traffic

Dhaka city is getting crowded and noisy day by day. Certain roads always remain blocked in congestion. In order that people avoid shortest routes, and hence the crowded roads, to reach destination, the city authority has made a new plan. Each junction of the city is marked with a positive integer (≤ 20) denoting the busyness of the junction. Whenever someone goes from one junction (the source junction) to another (the destination junction), the city authority gets the amount (busyness_of_destination− busyness_of_source)3 from the traveler. The authority has appointed you to find out the minimum total amount that it earns when someone goes from a certain junction (the zero point) to several others. Input The first line of each test case contains n (the number of junctions, 0 ≤ n ≤ 200) followed by n integers denoting the busyness of the junctions numbered 1 to n in that order. The next line contains r, the number of roads in the city. Each of the next r lines (one for each road) contains two junction-numbers (source, destination) that the corresponding road connects (all roads are unidirectional). The next line contains the integer q, the number of queries. The next q lines each contain a junction-number. Input is terminated by EOF. Output For each set of output, print the ‘Set #x’ (x = 1, 2, . . .) followed by q lines, one for each query, each containing the minimum total earning when one travels from junction 1 (the zero point) to the corresponding junction. However, for the queries that gives less than 3 units of minimum total earning, print a ‘?’. Sample Input 5 6 7 8 9 10 6 12 23 34 15 54 45 2 4 5 Sample Output Set #1 3 4