给定一个正整数 $N$。请构造一个 $(1, 2, \dots, N)$ 的置换序列 $p_1, p_2, \dots, p_K$，使其满足以下条件，或者报告无解。

• $0 \le K \le \lceil \log_2 N \rceil + 1$，其中 $K$ 为序列的长度。
• $p_1, p_2, \dots, p_K$ 是 $(1, 2, \dots, N)$ 的置换。换句话说，它们是从 $\{1, 2, \dots, N\}$ 到 $\{1, 2, \dots, N\}$ 的双射。
• 对于所有的 $x$ 和 $y$ ($1 \le x, y \le N$)，存在一个双射序列 $q_1, q_2, \dots, q_K$，使得 $(q_K \circ q_{K-1} \circ \dots \circ q_1)(x) = y$，且对于所有的 $i$，都有 $q_i = p_i$ 或 $q_i = p_i^{-1}$。

这里，$\circ$ 表示函数复合。当 $K=0$ 时，$q_K \circ q_{K-1} \circ \dots \circ q_1$ 定义为恒等函数。

输入格式

输入通过标准输入给出，格式如下：

$N$

数据范围： * $1 \le N \le 1000$

输出格式

如果无解，输出 $-1$。否则，按以下格式输出答案：

$K$ $p_{1,1} \ p_{1,2} \ \dots \ p_{1,N}$ $\vdots$ $p_{K,1} \ p_{K,2} \ \dots \ p_{K,N}$

这里，$p_{i,j}$ 必须是 $p_i(j)$ 的值。 如果存在多个解，输出其中任意一个即可。

样例

样例输入 1

3

样例输出 1

3
1 3 2
2 3 1
3 1 2

样例输入 2

4

样例输出 2

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

说明

考虑样例 1。例如，对于 $x = 2, y = 1$，我们可以令 $q_1 = p_1, q_2 = p_2^{-1}, q_3 = p_3$，从而得到 $q_3(q_2(q_1(2))) = 1$。