题目描述

小 D 最近学了有限自动机上用 LCC 维护的有限群分治 DFT，并得意地到处显摆。

大 D 看不下去了，给小 D 出了一个难题。

对于字符集大小为 $2$ 的非确定性有限自动机

定义 $L(G)$ 为最短的不能被 $G$ 接受的 01 串长度；如果不存在这样的串，则 $L(G)=0$。

大 D 限制了 $|V|\le n$。你需要构造一个自动机 $G$，使得 $L(G)$ 尽可能大。

自动机含义如下：

• $V$ 表示点集；
• $E_0,E_1$ 分别是两个定义在 $V$ 上的有向边集；
• $v_0\in V$ 表示起始点；
• $F\subseteq V$ 表示接受点集；
• 自动机 $G$ 接受长度为 $k$ 的 01 串 $S$，当且仅当存在点序列

满足 $v_k\in F$，且对所有 $i$，都有

输入格式

一行一个整数 $n$。

输出格式

输出自动机 $G$。要求：

首先输出 $E_0$：

第一行一个整数 $|E_0|$，满足

接下来 $|E_0|$ 行，每行两个整数 $u,v$，表示一条边 $(u,v)$。

然后以相同格式输出 $E_1$。

最后输出接受点集 $F$：

第一行一个整数 $|F|$。

接下来输出 $|F|$ 个整数，表示 $F$ 中的点。

样例

输入

3

输出

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

解释

最短的不可被接受的字符串是 1010。

数据范围与评分

本题只有两组数据：