Gifts

Interview

Time limit5sMemory limit1024 MB

Summary

Split candy packages numbered 1 to N into the largest number of children who each receive the same total candy count.

Level: Medium4 of 10
Topics: Math, Greedy, Implementation
Solved: No attempts yet

Problem

Bajtosia and Bajtek are preparing gifts for the students at their school for St. Nicholas Day. They agreed that the best gift is a lot of candy (not necessarily good for your teeth). Bajtek bought $N$ packages of candy. Package $i$ contains $i$ candies, for $i = 1, 2, \ldots, N$ .

Bajtosia wants to split all the candy among as many children as possible. She does not want to open the packages, and she does not want some children to receive a different number of candies than others. One child may receive several different packages.

Can you help? Write a program that finds the largest number of children among whom all the packages can be divided so that each child gets the same number of candies.

Input

The first and only line contains one natural number $N$ ( $1 \le N \le 200000$ ), the number of packages prepared by Bajtek.

Output

The first line of the output contains one natural number $R$ , the largest number of children that can receive gifts. The next $R$ lines describe the gifts, one child per line. The description for child $i$ starts with a natural number $R_i$ , the number of packages child $i$ receives, followed by a single space and then $R_i$ natural numbers, the numbers of candies in the packages given to that child.

If there are several solutions, your program may output any of them.

Examples2

Example 1
Input
```
3
```
Expected output
```
2
2 1 2
1 3
```
Example 2
Input
```
4
```
Expected output
```
2
2 1 4
2 2 3
```