题目描述

你在清理阁楼时发现了一箱旧游戏，其中有一副拼图。遗憾的是，包装已经破损，一些拼图片散落在箱底。你怀疑有些拼图片已经丢失，甚至由于阁楼十分混乱，箱子里可能还混入了其他拼图的碎片。

现在，你面前有一堆拼图片，希望把它们拼成一幅完整的矩形拼图。

更形式化地说：

• 一共有 $n$ 张正方形拼图片，编号为 $1$ 到 $n$。需要把它们边对边排列，组成一个矩形，并且必须使用全部 $n$ 张拼图片；
• 每张拼图片的边要么是直边，要么是不规则边。直边必须位于最终矩形的边界上，不规则边必须位于矩形内部；
• 所有不规则边的形状互不相同，每种边型恰好出现两次，并且出现在两张不同的拼图片上。两张拼图片只有在相邻边的形状相同时才能相邻放置；
• 可以旋转拼图片，但不允许将其翻面。

输入格式

输入包含：

• 第一行一个整数 $n$（$1\le n\le 3\times10^5$），表示拼图片数量；
• 接下来 $n$ 行，每行四个整数。第 $i$ 行按逆时针顺序给出第 $i$ 张拼图片四条边的连接类型。

连接类型 0 表示直边。

其余连接类型使用从 1 开始的连续正整数编号，每种非零连接类型恰好出现两次，并且这两次一定出现在两张不同的拼图片上。

输出格式

若无法按照要求拼成矩形，输出：

impossible

否则，按以下格式输出一个合法拼图：

• 第一行两个整数 $h,w$（$h,w\ge1$ 且 $h\times w=n$），表示矩形网格的高和宽；
• 接下来 $h$ 行，每行 $w$ 个整数，表示对应位置放置的拼图片编号。

正确答案的任意整体旋转均会被接受。

样例 1

输入

6
0 0 1 6
0 7 4 0
0 0 2 1
5 3 0 6
3 7 0 0
4 5 2 0

输出

2 3
1 4 5
3 6 2

样例 2

输入

4
0 0 1 2
0 0 2 3
0 0 3 4
0 0 1 4

输出

impossible

图示

样例一拼图示意图

上图展示了样例一的一种合法拼法。数字较大的编号表示拼图片编号，边缘附近的小数字表示边的连接类型。