Bob 昨天买了一个新的拼图。这个拼图由 $m^2$ 个矩形碎片组成，每块碎片都有一个从 $1$ 到 $m^2$ 的唯一编号，用于标识身份，并有四个关联数字表示相邻的碎片。

具体来说，编号为 $i$ 的碎片由四个数字 $n_i, s_i, w_i$ 和 $e_i$ 描述，分别对应四个相邻的碎片：编号为 $n_i$（分别为 $s_i, w_i$ 和 $e_i$）的碎片位于其北侧（分别为南侧、西侧和东侧）。如果关联数字为 $-1$，则表示该侧没有其他碎片。

毫无疑问，这个游戏的目标是将所有碎片排列在正确的位置。说明书上说，完整的图像是一个正方形，共有 $m$ 行 $m$ 列。

此时，Bob 正在银川参加国际大学生程序设计竞赛。他没有时间去拼拼图，但他必须解决 K 题。你能帮帮他吗？

输入格式

第一行包含一个整数 $m$ ($1 \le m \le 10^3$)。

接下来的 $m^2$ 行中，第 $i$ 行包含四个整数 $n_i, s_i, w_i$ 和 $e_i$ ($n_i, s_i, w_i, e_i \in \{-1\} \cup [1, m^2]$)。

保证存在对应的解。

输出格式

输出拼好的拼图，共 $m$ 行，从北向南排列，每行包含 $m$ 个整数，表示拼图中从西到东的碎片编号。

样例

输入 1

2
-1 3 -1 2
-1 4 1 -1
1 -1 -1 4
2 -1 3 -1

输出 1

1 2
3 4