酸奶瓶中生活着 $N$ 个细菌。但细菌们想要同伴，所以它们会形成菌落，过程如下。起初，每个细菌都是一个只包含它自身的菌落。当酸奶中至少还有两个菌落时，每一步都会选择距离最近的两个菌落并将它们合并。

起初，每对细菌 $u$ 和 $v$ 之间的距离 $d_{u,v}$ 是已知的。菌落 $G$ 和 $H$ 之间的距离计算为所有细菌对之间的平均距离：

$$\frac{1}{|G| \cdot |H|} \sum_{u \in G} \sum_{v \in H} d_{u,v}$$

细菌对精度的要求并不高——毕竟，你不能对单细胞生物奢求太多。因此，当存在多对菌落，其距离与最小距离之差在 $10^{-6}$ 以内时，这一步可以选择其中任意一对进行合并。

你需要模拟菌落合并的过程，并找到其中一种可能的方案。

输入格式

输入的第一行包含一个整数 $N$，表示细菌的数量（$2 \le N \le 2014$）。

接下来的 $N$ 行包含距离矩阵（$d_{i,j}$）的描述。每行包含 $N$ 个字符。第 $i$ 行第 $j$ 个位置的字符 $d_{i,j}$ 表示第 $i$ 个和第 $j$ 个细菌之间的距离。

保证对于所有 $i, j = 1, \dots, N$，有 $d_{i,i} = 0$，$d_{i,j} = d_{j,i}$ 且 $0 \le d_{i,j} \le 9$。

输出格式

给每个初始菌落编号为 $1$ 到 $N$。在第 $i$ 步（$i = 1, \dots, N - 1$）合并得到的菌落编号为 $N + i$。

输出应包含 $N - 1$ 行。第 $i$ 行必须包含三个数：在第 $i$ 步合并的两个菌落的编号，以及它们之间的距离，绝对或相对误差不超过 $10^{-6}$（$1 \le i \le N - 1$）。

样例

输入样例 1

4
0146
1025
4203
6530

输出样例 1

1 2 1.000000
3 4 3.000000
5 6 4.250000