今晚校园里有一场派对，$n$ 名男生和 $n$ 名女生将参加。他们打算互相亲吻，每个男生都要亲吻每个女生。但他们很注重安全，因为不想感冒。所以他们通过纸巾来亲吻，以防止微生物交换。如果每个人亲吻时使用的纸巾侧面从未被除他/她以外的任何人亲吻过，那么这个吻就是安全的，因此永远不会接触到别人的微生物。

学生们很狡猾，他们可以通过多张纸巾进行亲吻。在这种情况下，连接在一起的纸巾侧面在亲吻时会交换微生物。例如，如果男生 $X$ 在之前的某个吻中亲吻了纸巾 $A$ 的右侧，他就会把微生物留在这一侧，所以纸巾 $A$ 的右侧与纸巾 $B$ 的左侧相连，纸巾 $B$ 的左侧就会沾上 $X$ 的微生物，从而对其他人变得不安全。

不幸的是，他们只有 $\lfloor \frac{3n}{2} \rfloor$ 张纸巾，编号从 $1$ 到 $\lfloor \frac{3n}{2} \rfloor$。你需要输出 $n \cdot n$ 个男生和女生之间安全亲吻的序列。

输入格式

输入仅一行，包含一个正整数 $n$ ($n \leqslant 1000$)。

输出格式

输出 $n \cdot n$ 行，描述安全亲吻。每行描述包含由空格分隔的整数。描述以一对整数 $a$ 和 $b$ ($1 \leqslant a, b \leqslant n$) 开头，表示亲吻的男生和女生的编号。接下来是亲吻中使用的纸巾数量 $k$，随后是 $k$ 对整数 $c_i$ 和 $d_i$ ($1 \leqslant c_i \leqslant \lfloor \frac{3n}{2} \rfloor, 0 \leqslant d_i \leqslant 1$)，表示第 $i$ 张纸巾的编号以及靠近男生的那一侧（$0$ 表示左侧，$1$ 表示右侧）。纸巾按从男生到女生的方向列出。在一次亲吻中，所有纸巾必须各不相同。

你应该输出不超过 $5 \cdot 10^7$ 个整数。保证在给定约束条件下，这样的答案存在。

样例

输入 1

2

输出 1

1 1 2 1 0 2 0
1 2 1 1 0
2 1 1 2 0
2 2 2 2 0 1 0