Humanity's Last Code Exam / 2016_I / Road Times

## Problem Description

Ubol Narongdid is the founder of a brash new startup company called Special D-Liver-E. She wants to corner the market on overnight deliveries of organs between hospitals in the Phuket area. For scheduling purposes, it is important to have accurate estimates for the times to perform such deliveries. Several trips between various hospitals have already been performed, so delivery times between those pairs of hospitals are known. The company currently has software to estimate times for other (as yet untraveled) trips, but so far all the estimates have been woefully inaccurate.

You have been asked to come up with a method to improve these estimates. You have at your disposal the following information: 

1. The length (in kilometers) of the roads connecting each pair of cities in the Phuket area.
2. A set of times (in minutes) for various previously executed deliveries.

You know that roads are one-way, and each road has a fixed speed limit that lies between 30 and 60 kilometers per hour. Speed limits are real-valued and need not be integers. You also know that delivery trucks always take the route that minimizes distance traveled, and on each road will always travel at a constant speed equal to that road’s speed limit. Thus you know, for example, that if a given trip is 50 kilometers, the time it will take is between 50 and 100 minutes inclusive, in the absence of any other information. Ah, but you do have other information, namely the times of previous deliveries. It is up to you to use it to produce the best possible estimates.

### Input

The input starts with a line containing an integer n (1≤n≤30) indicating the number of cities, numbered 0 to n−1. After that are n lines each containing n integers specifying the distance in kilometers between cities: the j-th value on the i-th line indicates the distance when traveling directly from city i to city j. A value of −1 indicates there is no road directly connecting the two cities, and the distance from any city to itself is always 0; all other distances are positive and at most 1000. There are at most 100 roads.

Following this is a line with a single integer r (1≤r≤100) indicating the number of previously executed routes. The next r lines each contain three integers s, d, and t, where s and d are the source and destination cities and t is how long the delivery from s to d took, in minutes.

Finally, there is a line containing a single integer q (1≤q≤100) indicating the number of future delivery queries. The next q lines each contain two integers s and d giving the source and destination cities for the query.

You may assume that for each of the r+q source/destination pairs in the input there is a unique minimum-distance route.

### Output

Display a single line for each query containing the source and destination cities for that query, followed by the best low and high bounds on the estimate for the travel time, accurate to within an absolute or relative error of 10^(−6).

### Sample Input 1

## Problem Description

Ubol Narongdid is the founder of a brash new startup company called Special D-Liver-E. She wants to corner the market on overnight deliveries of organs between hospitals in the Phuket area. For scheduling purposes, it is important to have accurate estimates for the times to perform such deliveries. Several trips between various hospitals have already been performed, so delivery times between those pairs of hospitals are known. The company currently has software to estimate times for other (as yet untraveled) trips, but so far all the estimates have been woefully inaccurate.

You have been asked to come up with a method to improve these estimates. You have at your disposal the following information: 

1. The length (in kilometers) of the roads connecting each pair of cities in the Phuket area.
2. A set of times (in minutes) for various previously executed deliveries.

You know that roads are one-way, and each road has a fixed speed limit that lies between 30 and 60 kilometers per hour. Speed limits are real-valued and need not be integers. You also know that delivery trucks always take the route that minimizes distance traveled, and on each road will always travel at a constant speed equal to that road’s speed limit. Thus you know, for example, that if a given trip is 50 kilometers, the time it will take is between 50 and 100 minutes inclusive, in the absence of any other information. Ah, but you do have other information, namely the times of previous deliveries. It is up to you to use it to produce the best possible estimates.

### Input

The input starts with a line containing an integer \( n \) (\( 1 \leq n \leq 30 \)) indicating the number of cities, numbered 0 to \( n - 1 \). After that are \( n \) lines each containing \( n \) integers specifying the distance in kilometers between cities: the \( j \)-th value on the \( i \)-th line indicates the distance when traveling directly from city \( i \) to city \( j \). A value of \(-1\) indicates there is no road directly connecting the two cities, and the distance from any city to itself is always 0; all other distances are positive and at most 1000. There are at most 100 roads.

Following this is a line with a single integer \( r \) (\( 1 \leq r \leq 100 \)) indicating the number of previously executed routes. The next \( r \) lines each contain three integers \( s \), \( d \), and \( t \), where \( s \) and \( d \) are the source and destination cities and \( t \) is how long the delivery from \( s \) to \( d \) took, in minutes.

Finally, there is a line containing a single integer \( q \) (\( 1 \leq q \leq 100 \)) indicating the number of future delivery queries. The next \( q \) lines each contain two integers \( s \) and \( d \) giving the source and destination cities for the query.

You may assume that for each of the \( r+q \) source/destination pairs in the input there is a unique minimum-distance route.

### Output

Display a single line for each query containing the source and destination cities for that query, followed by the best low and high bounds on the estimate for the travel time, accurate to within an absolute or relative error of \( 10^{-6} \).

### Sample Input 1