Fibonacci Souvenirs

The Fibonacci sequence is defined as follows.

• $F\_1=1$
• $F\_2=1$
• $F\_n=F\_{n-1}+F\_{n-2}$ (where $n\ge 3$)

Jeonghwi bought $N$ souvenirs with Fibonacci numbers written on them at a market in Luxor, Egypt. The souvenir numbered $x(1\le x\le N)$ has $F\_x$ written on it.

Jeonghwi wants to give souvenirs to Serim and Seongju, who both like the Fibonacci sequence. If one person receives too many souvenirs, the person with fewer may be sad. So the souvenirs must be split so that the sum of the Fibonacci numbers each person receives is equal. Depending on $N$, not all $N$ souvenirs can be distributed, and in that case the number of souvenirs given out must be as large as possible.

Split the souvenirs so that the number of souvenirs given out is maximized and the sums of the numbers each person receives are equal. A way to split them so that each person gets at least one souvenir always exists.

The first line contains the number of souvenirs $N$ that Jeonghwi bought.

On the first line, print the number $X$ of souvenirs Serim receives.

On the second line, print the numbers $A\_1,A\_2,\cdots ,A\_X$ of the souvenirs Serim receives, separated by spaces.

On the third line, print the number $Y$ of souvenirs Seongju receives.

On the fourth line, print the numbers $B\_1,B\_2,\cdots ,B\_Y$ of the souvenirs Seongju receives, separated by spaces.

If there are several valid distributions, print any one of them.

• $2\le N\le 2\,000$
• $X,Y\ge 1$
• $1\le A\_i\le N(1\le i\le X)$
• $1\le B\_j\le N(1\le j\le Y)$
• $A\_1,A\_2,\cdots ,A\_X,B\_1,B\_2,\cdots ,B\_Y$ are distinct numbers.
• All numbers in the input are integers.