Clubs

Citizens of town X love to participate in different clubs. During the years, the count of clubs in the town increased dramatically and now there are many clubs with the same participants in them. City’s government decided that it is time to introduce some order in city’s clubs. Decision was taken that club’s system in town should meet the following requirement:

• For each pair of citizens there is at least one club, such that one of those two persons is a member of that club and the other is not.

• A citizen can be a member of many clubs, as well as may participate in none of them.

As maintenance of each club requires expenses, the total number of clubs should be minimized. In addition, the members of each club should gather for meetings and there are no halls big enough in the city. As a result, the number of members in the biggest club (i.e. with the biggest number of ranking members) should be minimized, too (of course there may be more than one 'biggest' clubs with equal number of members).

There are n citizens in the town X and they are numbered from 1 to n.

Write a program, which finds the minimum number of clubs, which satisfy the first requirement. The program should determine the members of each club as well, so that the biggest club would be with minimum members. If there are more than one solution, the program should find any of them.

Input

A single integer n (2 ≤ n ≤ 10^5) - the number of citizens in town X.

Output

On the first row print two spaceseparated integers – the minimal number of clubs, which can satisfy first requirement, and the minimal number of members in the biggest club.

After that, your program should output one row with space-separated integers for each club in the found set. The first number in each row shows the members' count in the corresponding club. A list of all its members (ordered no matter how) should complete the line.

Examples

Note

We can satisfy first requirement with minimum three clubs and the biggest club can have minimum 2 members. First requirement can be also met with following set of clubs: {2, 4, 5}, {3, 4} and {5}, but in that case the biggest club has 3 members.