Marie 喜欢多米诺骨牌。她还太小，无法完全理解这个游戏，所以她只是根据以下简单规则来创建排列：多米诺骨牌的每一端都必须与另一块多米诺骨牌上标有相同数字的一端相邻。

图 D.1：第一个样例测试用例的可视化。

今天，Marie 发现了一大盒空白的多米诺骨牌。这让她非常兴奋，因为她现在可以充分发挥创造力：首先创建一个不受限制的排列，然后在第二步中，在所有多米诺骨牌的两端涂上数字，使得她的简单规则得到满足。

她已经决定，在每块多米诺骨牌的两端写上相同的数字对她来说不够令人满意。她希望每个数字最多只使用两次。然而，她并不限制自己只能使用 0 到 6 之间的数字，也不介意两块多米诺骨牌是否有相同的数字对。

Marie 将多米诺骨牌放置在整数网格上，使得每块多米诺骨牌恰好占据两个相邻的网格方块。注意，Marie 的排列不一定必须是连通的。

在 Marie 决定好排列方式后，她发现选择合适的数字比预想的要困难。请帮助她为给定的排列找到一种有效的编号方式，或者说明这是不可能的。

输入格式

输入包含： 一行一个整数 $n$ ($2 \le n \le 5\,000$)，表示 Marie 排列中多米诺骨牌的数量。 $n$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ ($1 \le x_1, y_1, x_2, y_2 \le 10\,000$)，其中 $(x_1, y_1)$ 和 $(x_2, y_2)$ 是其中一块多米诺骨牌两端的网格位置。

保证所有多米诺骨牌都占据整数网格上的两个相邻位置，且没有两块多米诺骨牌重叠。

输出格式

如果存在有效的编号方式，请打印 $n$ 行，第 $i$ 行包含两个整数，即 Marie 应该写在第 $i$ 块多米诺骨牌两端的数字。输出数字的顺序应与输入中多米诺骨牌（包括其两端）出现的顺序相同。输出中的所有数字应为 $0$ 到 $10^6$ 之间的整数（包含边界）。如果存在多种有效的编号方式，你可以输出其中任意一种。如果不存在有效的编号方式，则输出 impossible。

样例

样例输入 1

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

样例输出 1

0 3
1 2
0 2
3 1

样例输入 2

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

样例输出 2

impossible