The Company

 

            There are N people working in a company. Every person is employed in one of the departments of the company and is either a BOSS or a simple EMPLOYEE. Every boss interacts with every employee in his department (but not with other bosses). The degree of efficiency of a department is equal to the number of distinct interactions (boss,employee) which take place in that department. The efficiency of the whole company is the sum of the degrees of efficiency of every department.

            The manager of the company knows that the efficiency of the company is E. However, in order for it to be a relevant proof of good management, the efficiency has to be achieved using a minimal number of persons. If the efficiency can be achieved in more than one way, with the same minimal number of persons, then the total number of bosses in the company has to be minimum.

            You have to find the minimum number of persons N and the minimum number of bosses S with whom the efficiency E can be achieved. Plus, you have to determine the structure of the company, specifying the number of departments and for every department, the total number of people working in that department (including the bosses) and the number of bosses working there.

 

Input Data

            In the input file COMP.IN there will be a single integer: E.

 

Output Data

            The first line of the output file COMP.OUT will contain the numbers N,S and K, separated by blanks, meaning the minimum number of people, the minimum number of bosses and the number of departments of the company. On the next K lines, there will be 2 integers: Pi and Si, separated by a blank, representing the number of people working in the department #i and the number of bosses (if there are Si bosses, then there wil be Pi-Si simple employees in that department). If there are more solutions for the structure of the company, then you can print any of them.

 

Limits:

·                     1 <= E <= 2000

·                     The company must have at least one department.

·                     S1+S2+..+Sk=S

 

Example

COMP.IN                    COMP.OUT

7                          7 3 2

                           2 1

                           5 2

 

 

Time limit: 1 second/test case