Julia 的 $n$ 位朋友想要在他们搬到的新国家创办一家初创公司。他们根据各自的工作内容，从最前端的任务到最后端，给彼此分配了从 $1$ 到 $n$ 的编号。他们还估计了一个矩阵 $c$，其中 $c_{ij} = c_{ji}$ 表示从事工作 $i$ 和 $j$ 的人之间每月平均通信的消息数。

现在他们想要建立一棵层级树。这是一棵二叉树，每个节点包含团队中的一名成员。其中一名成员将被选为团队领导，并位于根节点。为了让领导能够轻松联系到任何下属，对于树中的每个节点 $v$，必须满足以下条件：其左子树中的所有成员编号都必须小于 $v$，其右子树中的所有成员编号都必须大于 $v$。

层级树确定后，从事工作 $i$ 和 $j$ 的人将通过树中连接他们节点的唯一最短路径进行通信。设该路径的长度为 $d_{ij}$。因此，他们通信的成本为 $c_{ij} \cdot d_{ij}$。

你的任务是找到一棵层级树，使得所有对的通信总成本最小化： $$\sum_{1 \le i < j \le n} c_{ij} \cdot d_{ij}$$

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200$)，表示组织初创公司的团队成员人数。 接下来的 $n$ 行，每行包含 $n$ 个整数，第 $i$ 行的第 $j$ 个数字为 $c_{ij}$，表示团队成员 $i$ 和 $j$ 之间每月估计的通信消息数 ($0 \le c_{ij} \le 10^9$; $c_{ij} = c_{ji}$; $c_{ii} = 0$)。

输出格式

输出一棵使通信总成本最小化的层级树的描述。为此，对于从 $1$ 到 $n$ 的每位团队成员，输出其父节点的成员编号，如果是领导则输出 $0$。如果存在多个最优树，输出其中任意一个即可。

样例

输入 1

4
0 566 1 0
566 0 239 30
1 239 0 1
0 30 1 0

输出 1

2 4 2 0

说明

最小可能的总成本为 $566 \cdot 1 + 239 \cdot 1 + 30 \cdot 1 + 1 \cdot 2 + 1 \cdot 2 = 839$：