Дистанционный практикум по программированию

All who read N. N. Nosov's books about the adventures of the boy called Dunno and his friends remember Dunno painting portraits and writing poems. But few know that Dunno also wrote several novels that attained widespread popularity. The novels featured his friends. One of them, Knowall, has closely studied Dunno's literary work and noted an interesting thing.

For each of Dunno's friends it is possible to select some novels where he takes part but no other friend takes part in all of these novels.

It is known that Dunno had n friends. Knowall wondered what was the smallest number of novels that Dunno could have produced to keep the property noted above.

For example, if Dunno had three friends Bolt, Nut, and Flower, he could have done with just three novels: first about Bolt and Nut, the second about Bolt and Flower, and the third about Nut and Flower. The only common character for the first and second novels will be Bolt, for the first and third Nut, for the second and the third Flower.

To make it easier to reason about the problem, Knowall has numbered Dunno's friends from 1 to n. Characters in each novel form a subset of the natural numbers from 1 to n. To find the common characters in the novels you take the intersection of the corresponding subsets. Initially Knowall had thought that at least n novels were necessary. But it turned out to be false. For example, for n = 7 one can do with 6 novels, with characters {1, 2, 3, 4, 5}, {1, 7}, {2, 3, 4, 6, 7}, {2, 5, 6}, {3, 5, 6, 7}, {4, 6}.

Then each friend can be found as the only common character of some novels:

                            {1} = {1, 2, 3, 4, 5} ∩ {1, 7}

                            {2} = {1, 2, 3, 4, 5} ∩ {2, 3, 4, 6, 7} ∩ {2, 5, 6}

                            {3} = {1, 2, 3, 4, 5} ∩ {2, 3, 4, 6, 7} ∩ {3, 5, 6, 7}

                            {4} = {1, 2, 3, 4, 5} ∩ {4, 6}

                            {5} = {1, 2, 3, 4, 5} ∩ {2, 5, 6} ∩ {3, 5, 6, 7}

                            {6} = {2, 5, 6} ∩ {4, 6}

                            {7} = {1, 7} ∩ {3, 5, 6, 7}

 Write a program that for given n finds a collection of novels that possesses the property noted by Knowall. The collection must consist of the smallest possible number of novels.

 

Limitations

1 <= n <= 10 000.

 

Input

The first line contains single integer n – the number of Dunno’s friends.

 

Output

The first line of the output file should contain single integer m – the smallest number of novels that Dunno must write. On each of the following m lines should contain the space delimited numbers of characters of the corresponding novel.

 

Example

Input	Output
5	4 1 2 3 1 4 2 4 5 3 5

 

 

All Rybinsk-2012 problems (in PDF)