시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB111100.000%

문제

You are given a positive integer $N$. Construct a sequence of permutations of $(1,2,\cdots,N)$, $p_1,p_2,\ldots,p_K$, that satisfy following conditions, or report that it's impossible.

  • $0 \leq K \leq \lceil \log_2 N \rceil + 1$, where $K$ is the length of the sequence.
  • $p_1,p_2,\ldots,p_K$ are permutations of $(1,2,\ldots,N)$.

In other words, they are bijections from $\{1,2,\ldots,N\}$ to $\{1,2,\ldots,N\}$.

  • For all $x$ and $y$ ($1 \leq x,y \leq N$), there is a sequence of bijections $q_1,q_2,\ldots,q_K$ such that $(q_K \circ q_{K-1} \circ \cdots \circ q_1)(x) = y$ and $q_i=p_i$ or $p_i^{-1}$ for all $i$.

Here, $\circ$ denotes function composition, and when $K=0$, $q_K \circ q_{K-1} \circ \cdots \circ q_1$ is defined as an identity function.

입력

Input is given from Standard Input in the following format:

$N$

출력

If there is no solution, print $-1$. Otherwise, print the answer in the following format:

$K$

$p_{1,1}$ $p_{1,2}$ $\cdots$ $p_{1,N}$

$\vdots$

$p_{K,1}$ $p_{K,2}$ $\cdots$ $p_{K,N}$

Here, $p_{i,j}$ must be a value of $p_i(j)$.

If there are multiple solutions, you can print any of them.

제한

  • $1 \leq N \leq 1000$

예제 입력 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

노트

In Sample 1 for $x=2,y=1$, we can set $q_1 = p_1, q_2 = p_2^{-1}, q_3 = p_3$ and get $q_3(q_2(q_1(2)))=1$.