GLASS2 - The Glazier 2

no tags 

Jozo the glazier has once again made N square pieces of glass. The dimensions (sides) of these squares are equal to 1, 2, 3, ..., N - therefore, the areas of these squares equal to 12, 22, 32, ..., N2.

Four customers have arrived once again. This time Jozo will sell all N squares of glass. Again, each of the customers must get the same total area of glass (which equals the total area of all N squares divided by four).

Help Jozo and divide his N pieces of glass among the four customers. Assume that the solution (not necesarily unique) exists in all of the test data.

Input

An integer N (10 ≤ N ≤ 60).

Output

In the first line, print four numbers: the number of pieces of glass assigned to the first, to the second, to the third and to the fourth customer (respectively).

In ith of the next four lines, print the dimensions of the squares of glass assigned to the ith customer. (Each square must be assigned to exactly one customer.)

Example

Input:
15

Output:
4 4 4 3
3 6 11 12
4 5 10 13
1 7 8 14
2 9 15

hide comments
vengatesh15: 2017-02-18 19:17:47

easy one..

Aditya Pande: 2012-12-29 11:12:36

is it related to GLASS?

Ehor Nechiporenko: 2012-12-26 10:37:11

Strange, that only a few people has resolved this problem.


Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:0.199s-1.393s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:originated from a mathematical problem