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

Ufa SATU contest. Petrozavodsk training camp. Summer 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. The Captain's Squad

Time limit: 1.0 second
Memory limit: 64 MB
A squad consists of n soldiers. Every day exactly three of them must go on duty.
Captain Obvious started to form a duty chart. But suddenly he encountered with the obvious fact that any two soldiers who were on duty together begin to annoy each other. If two soldiers were on duty together for three times, then the fourth co-duty can make them so angry that obviously something really bad would happen.
So the Captain wants to make a duty chart for the maximal possible number of days so that any two soldiers would have at most three co-duties. Unfortunately it's far from obvious to the Captain how to do it, so he hopes that you can help him.

Input

The first line contains an odd integer n (3 ≤ n ≤ 99).

Output

The first line should contain one integer k, the maximal number of days in a duty chart. The i-th of the following k lines should contain three space-separated numbers of soldiers that should go on duty on the i-th day. Soldiers are numbered with integers from 1 to n.

Samples

inputoutput
3
3
1 2 3
2 3 1
3 1 2
5
10
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Problem Author: Artyom Ripatti
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009
To submit the solution for this problem go to the Problem set: 1744. The Captain's Squad