Doremy 有一棵边权为整数的树，节点数为 $n$，边权在 $1$ 到 $10^9$ 之间。她在这棵树上进行了 $\frac{n(n+1)}{2}$ 次实验。

在每次实验中，Doremy 选择两个节点 $i$ 和 $j$ 满足 $j \le i$，并用一条权值为 $1$ 的边直接连接它们。此时，图中会产生恰好一个环（当 $i = j$ 时为自环）。Doremy 将 $f(i, j)$ 定义为所有节点到该环的最短路径长度之和。

形式化地，令 $\operatorname{dis}_{i,j}(x, y)$ 表示添加权值为 $1$ 的边 $(i, j)$ 后，节点 $x$ 与 $y$ 之间的最短路径长度；令 $S_{i,j}$ 表示添加边 $(i, j)$ 后处于环上的节点集合。则：

$$f(i, j) = \sum_{x=1}^{n} \left( \min_{y \in S_{i,j}} \operatorname{dis}_{i,j}(x, y) \right)$$

Doremy 记录下了所有满足 $1 \le j \le i \le n$ 的 $f(i, j)$ 的值，然后便去睡觉了。然而，当她醒来时，发现那棵树不见了。幸运的是，$f(i, j)$ 的值仍然保存在她的笔记本上，并且她知道每个值对应的是哪一组 $i$ 和 $j$。给定这些 $f(i, j)$ 的值，你能帮她恢复这棵树吗？

保证至少存在一棵满足条件的树。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 2000$）—— 树中节点的数量。

接下来的 $n$ 行包含一个下三角矩阵，第 $i$ 行有 $i$ 个整数；第 $i$ 行的第 $j$ 个整数为 $f(i, j)$（$0 \le f(i, j) \le 2 \cdot 10^{15}$）。

保证存在一棵边权在 $1$ 到 $10^9$ 之间的树，其对应的 $f(i, j)$ 值与输入中给出的值一致。

输出格式

输出 $n - 1$ 行，描述这棵树。在输出的第 $i$ 行中，输出三个整数 $u_i, v_i, w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$），表示一条连接 $u_i$ 和 $v_i$ 且权值为 $w_i$ 的边。

如果存在多个答案，你可以输出其中任意一个。

所有的边必须构成一棵树，且所有的 $f(i, j)$ 值必须与输入中给出的值一致。

样例

输入 1

3
7
3 5
0 2 8

输出 1

2 3 3
1 2 2

输入 2

9
8081910646
8081902766 8081903751
8081902555 8081903540 8081905228
3090681001 3090681986 3090681775 7083659398
7083657913 7083658898 7083658687 2092437638 15069637722
1748216295 1748217280 1748217069 5741194692 749972427 10439821163
2377558289 2377559274 2377559063 6370536686 1379314421 5028071980 8866466178
1746983932 1746984917 1746984706 5739962329 748740064 10438588800 5026839617 10448447704
2341942133 2341943118 2341942907 6334920530 1343698265 4992455824 8830850022 4991223461 9115779270

输出 2

1 2 985
2 3 211
2 4 998244353
2 5 998244853
4 6 671232353
6 8 1232363
4 7 356561356
7 9 35616156

说明

在第一个样例中，下图从左到右、从上到下分别展示了当连接点对 $(1, 1)$、$(1, 2)$、$(1, 3)$、$(2, 2)$、$(2, 3)$、$(3, 3)$ 时的图。黄色标记的节点在环上。