F. Fighting in Group
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ cats here, numbered from $$$1$$$ to $$$n$$$. They desire to fight.

We call the cat numbered $$$i$$$ as "Cat $$$i$$$". For every $$$i \in [1, n]$$$, Cat $$$i$$$ wants to fight with every nonadjacent cat.

For example, when $$$n = 4$$$, Cat $$$1$$$ wants to fight with $$$3$$$ and $$$4$$$, Cat $$$2$$$ wants to fight with $$$4$$$, Cat $$$3$$$ wants to fight with $$$1$$$, Cat $$$4$$$ wants to fight with $$$1$$$ and $$$2$$$.

You should arrange rounds to satisfy their desires. In each round, you can choose some cats from them, and divide the chosen cats into two nonempty groups. Obviously, a cat can't appears in both groups in a single round.

And in this round, every pair $$$(i, j)$$$ which Cat $$$i$$$ and $$$j$$$ is chosen and set in different groups will fight with each other.

Be careful, you cannot arrange adjacent cats to fight in any round. They will feel unhappy. Formally, if you want to choose Cat $$$i$$$ and Cat $$$i+1$$$ in a round, they should in the same group.

For example, you can arrange $$$[1, 2, 4]$$$ to fight with $$$[6, 7]$$$. But you can't arrange $$$[1, 2, 4]$$$ to fight with $$$[3, 6, 7]$$$, because $$$3$$$ don't want to fight with $$$2$$$ or $$$4$$$.

We don't care about how many fights actually happened in all rounds. In other words, for each pair $$$(i, j)$$$ when $$$|i-j| \gt 1$$$, they should fight at least once in all rounds. Arrange two cats to fight again and again is not banned, although it may be useless.

To save time, you should find the minimum number of rounds to satisfy them all, and how to arrange each round.

If there are mutiple solutions, output any of them.

Input

The input contains an integer $$$n$$$ ($$$3 \leq n \leq 10^3$$$) — the number of cats waiting for fight.

Output

The first line contains an integer $$$m$$$ — the number of rounds you arrange.

The following $$$2m$$$ lines shows each round you arrange. For each round, print two lines for your two groups:

The first line contains $$$n_1$$$ — the number of cats in first group, and followed with $$$n_a$$$ integers $$$a_1, a_2, ... a_{n_1}$$$, donates the cat's id.

The second line is similar, contains $$$n_2$$$ and $$$b_1, b_2, ... b_{n_2}$$$.

Examples
Input
3
Output
1
1 1 
1 3
Input
4
Output
2
2 1 2 
1 4 
1 1 
1 3
Note

In the first example, we only need one round to let Cat $$$1$$$ and Cat $$$3$$$ fight with each other.

In the second example, we can prove $$$2$$$ is the minimum rounds we need. $$$(1, 3), (1, 4), (2, 4)$$$ needs to fight in this example. And there are many correct solutions for $$$n = 4$$$. The following solution is considered correct too:

2

1 1

2 4 3

2 1 2

1 4