ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Winter 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Flags for Provinces

Time limit: 1.0 second
Memory limit: 64 MB
The government of Cuckooland decided that each province of such a huge country should have its own flag. A famous painter Cuckooshkin was told to create all flags. It is known that Cuckooshkin uses only n different colors in his paintings. According to the government's plan, every two flags of provinces should have at least one common color, which will symbolize integrity of the country. On the other hand, the painter wants to make these flags as varicoloured as possible, so he doesn't want any colour to occur in three or more flags. What is the maximal number of flags Cuckooshkin can create without breaking neither his own nor government's requirements?

Input

The first line contains the only integer n (3 ≤ n ≤ 1000), the number of colors the painter can use. The colors are numbered 1 to n.

Output

In the first line output the integer k, the maximal number of flags the painter can create. Each of the next k lines should contain description of the next flag: first, the number of colors used in it and then the numbers of these colors. All integers in this line should be separated by single space. In case there are many correct answers, you can output any of them.

Sample

inputoutput
4
3
2 1 2
2 1 3
2 2 3
Problem Author: Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009
To submit the solution for this problem go to the Problem set: 1692. Flags for Provinces