도로 주행 시간 추정

어떤 배송 회사가 밤마다 병원 사이로 장기를 옮긴다. 배차 계획을 세우려면 배송에 걸리는 시간을 정확히 예측해야 한다.

도시의 모든 도로는 일방통행이고, 도로마다 시속 30킬로미터 이상 60킬로미터 이하의 제한 속도가 하나씩 정해져 있다. 제한 속도는 실수이며 정수가 아니어도 된다. 배송 트럭은 출발 도시에서 도착 도시까지 총 거리가 가장 짧은 경로로만 달리고, 그 경로의 각 도로를 그 도로의 제한 속도와 같은 일정한 속도로 달린다. 그래서 길이가 50킬로미터인 도로 하나만 놓고 보면 통과 시간은 50분 이상 100분 이하다.

이미 마친 배송 $r$건의 소요 시간을 알고 있다. 이 기록으로 앞으로의 배송 시간을 더 좁게 예측하려고 한다. 질의마다, 기록된 시간을 모두 설명하는 제한 속도 배정을 전부 살펴 가능한 가장 짧은 주행 시간과 가장 긴 주행 시간을 구하라.

첫째 줄에 도시의 수 $n$ ($1 \le n \le 30$)이 주어진다. 도시 번호는 $0$번부터 $n-1$번까지다.

다음 $n$개 줄에는 각각 정수 $n$개가 주어진다. $i$번째 줄의 $j$번째 값은 도시 $i$에서 도시 $j$로 곧장 이어지는 도로의 길이(킬로미터)이고, 그런 도로가 없으면 $-1$이다. 대각선 값은 항상 $0$이고, 나머지 길이는 $1$ 이상 $1000$ 이하이며, 도로는 최대 $100$개다.

다음 줄에 기록된 배송의 수 $r$ ($1 \le r \le 100$)가 주어진다. 이어지는 $r$개 줄에는 각각 정수 $s$, $d$, $t$가 주어진다. 도시 $s$에서 도시 $d$로 간 배송이 $t$분 걸렸다는 뜻이다.

다음 줄에 질의의 수 $q$ ($1 \le q \le 100$)가 주어진다. 이어지는 $q$개 줄에는 각각 정수 $s$와 $d$가 주어진다.

입력에 나오는 $r+q$개의 쌍 $(s, d)$는 모두 $s \ne d$이고, 도시 $s$에서 도시 $d$로 갈 수 있으며, 거리가 최소인 경로가 하나뿐이다. 기록된 시간 $r$개를 모두 만족시키는 제한 속도 배정이 적어도 하나 있다.

질의마다 한 줄씩, 입력에 주어진 순서대로 출력한다. 각 줄에는 출발 도시, 도착 도시, 가능한 가장 짧은 주행 시간, 가능한 가장 긴 주행 시간을 공백 하나로 구분해 출력한다. 두 시간은 소수점 아래 여섯째 자리까지 반올림해서 적는다.