非确定性有限自动机 (NFA) 定义为 $G = (V, E_0, E_1, v_0, F)$，其中 $(V, E_0)$ 和 $(V, E_1)$ 构成两个有向图，$v_0 \in V$ 是初始顶点，$F \subseteq V$ 是接受顶点集。

我们称 NFA $G$ 识别一个 01 字符串 $s = s_1s_2 \dots s_n$，当且仅当存在一个顶点序列 $u_0, u_1 \dots u_n$，使得 $u_0 = v_0$，对于所有 $i = 1, 2, \dots, n$ 都有边 $\langle u_{i-1}, u_i \rangle \in E_{s_i}$，且 $u_n \in F$。

定义 $L = L(G)$ 为使得存在一个长度为 $L$ 且 $G$ 无法识别的字符串 $s$ 的最小非负整数。如果对于 $G$ 不存在这样的 $L$，则定义 $L(G) = -1$。

给定 $n$，你需要构造一个 NFA $G = (V, E_0, E_1, v_0, F)$，使得 $|V| = n$ 且 $L(G)$ 足够大。关于 $n$ 和 $L(G)$ 的具体限制见文末。

输入格式

输入的第一行包含一个整数 $n$。

输出格式

输出你构造的 NFA $G$。 假设 $V$ 中的顶点标记为整数 $0, 1, \dots, n - 1$。

首先，按以下格式输出 $E_0$：第一行包含一个整数 $e = |E_0|$ ($0 \le e \le 1000$)。 随后有 $e$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($0 \le x_i, y_i < n$)，表示存在一条边 $\langle x_i, y_i \rangle \in E_0$。注意允许 $x_i = y_i$。

其次，以与 $E_0$ 相同的格式打印 $E_1$。

接下来，打印一行包含整数 $k$。

最后，打印一行包含 $k$ 个整数 $f_1, f_2, \dots, f_k$，表示 $F = \{f_1, f_2, \dots, f_k\}$。

样例

以下是一个不出现在测试用例中的示例。在此例中，$L(G) = 4$，因为 $G$ 无法识别字符串 “1010”。

样例输入 1

3

样例输出 1

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

说明

本题有两个测试用例：$n = 6$ 和 $n = 20$。

当 $n = 6$ 时，你的输出的 $L(G)$ 应严格大于 $18$。

当 $n = 20$ 时，你的输出的 $L(G)$ 应严格大于 $400$。