说明

Bob昨天买了一个新的拼图游戏。这个拼图由m^2个矩形块组成，每个块都有一个从1到m^2的唯一数字用于识别，还有四个相关的数字表示相邻的块。

具体来说，编号为i的拼图用四个数字n, s, w, e对应四个相邻的块: n对应的块位于该块拼图的北边, 以此类推. 如果这个相关的数字是-1，就没有更多的块在相应的一边。

毫无疑问，这款游戏的目标是将所有棋子排列在正确的位置

你能帮帮Bob么?

输入格式

输入第一行包含一个整数m (1 <= m <= 10^3)

接下来的m^2行, 第i行包括四个整数ni, si, wi, ei, (ni, si, wi, ei∈{-1}∪[1, m^2])

数据保证有解

输出格式

输出一个m*m的矩阵, 表示最后拼图的样子

样例

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

1 2
3 4