Ubol Narongdid 是一家名为 Special D-Liver-E 的新兴初创公司的创始人。她希望垄断普吉岛地区医院之间器官的隔夜配送市场。为了进行调度，准确估计此类配送所需的时间非常重要。由于已经执行了多次医院之间的行程，因此已知这些医院对之间的配送时间。该公司目前有软件来估计其他（尚未行驶的）行程的时间，但到目前为止，所有的估计都非常不准确。

你被要求提出一种改进这些估计的方法。你可以利用以下信息：1) 普吉岛地区连接每对城市之间的道路长度（以公里为单位），以及 2) 一组先前执行的配送行程所花费的时间（以分钟为单位）。

你知道道路是单向的，每条道路都有一个介于每小时 30 到 60 公里之间的固定限速。限速是实数值，不一定是整数。你还知道，配送卡车总是选择距离最短的路线，并且在每条道路上始终以等于该道路限速的速度行驶。因此，例如，你知道如果某次行程为 50 公里，在没有其他信息的情况下，它所需的时间在 50 到 100 分钟之间（含边界）。啊，但你确实有其他信息，即之前配送的时间。如何利用这些信息来产生尽可能好的估计，就取决于你了。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 30$)，表示城市数量，编号为 $0$ 到 $n-1$。接下来有 $n$ 行，每行包含 $n$ 个整数，指定城市之间的距离（以公里为单位）：第 $i$ 行的第 $j$ 个值表示直接从城市 $i$ 到城市 $j$ 行驶的距离。值为 $-1$ 表示没有直接连接这两个城市的道路，任何城市到自身的距离始终为 $0$；所有其他距离均为正数且最多为 $1\,000$。道路总数最多为 $100$ 条。

接下来是一行，包含一个整数 $r$ ($1 \le r \le 100$)，表示先前执行的路线数量。接下来的 $r$ 行，每行包含三个整数 $s$、$d$ 和 $t$，其中 $s$ 和 $d$ 分别是起点和终点城市，$t$ 是从 $s$ 到 $d$ 的配送所花费的时间（以分钟为单位）。

最后是一行，包含一个整数 $q$ ($1 \le q \le 100$)，表示未来的配送查询数量。接下来的 $q$ 行，每行包含两个整数 $s$ 和 $d$，给出查询的起点和终点城市。

你可以假设输入中每一对 $r+q$ 个起点/终点对都有唯一的最小距离路线。

输出格式

对于每个查询，输出一行，包含该查询的起点和终点城市，随后是旅行时间估计的最佳下界和上界，精确到 $10^{-6}$ 的绝对或相对误差。

样例

样例输入 1

3
0 50 -1
55 0 40
-1 40 0
1
0 2 120
3
0 1
1 2
1 0

样例输出 1

0 1 50.0 80.0
1 2 40.0 70.0
1 0 55.0 110.0