GLASS - The Glazier

Jozo the glazier has 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. Each of them buys exactly 3 pieces of of glass (Jozo will therefore sell exactly 12 pieces of glass). Each customer has stated that the sum of the dimensions of the squares he gets must be equal to N (for example he could get the pieces with dimensions 1, 2 and N-3).

Furthermore, since all customers pay the same price, Jozo wants to be fair and ensure that the sum of areas of the 3 squares must be equal for each customer (but this sum is not defined in advance). Help Jozo to choose which pieces to sell.

Input

A natural number N (12 ≤ N ≤ 1500).

Output

Print -1 if there is no solution. Otherwise, print four lines: in each of these four lines there must be three numbers from the set {1, 2, ..., N} and their sum must be equal to N. Also, the sum of squares of these three numbers must be constant for each row. All 12 numbers must be distinct.

Example

Input:
84

Output:
17 33 34
18 29 37
19 27 38
22 23 39

Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:that would be me

hide comments
2019-11-27 00:02:40 Petar Bosnjak
Is O(n^2*log(n^2)) intended complexity?
2016-03-21 18:30:48
Seems to be too slow using the semi-brute force approach. Any ideas on how I could improve it? Also has anyone solved this in Python?
2014-04-10 10:28:50 Ikshu Bhalla
@Hunters Den: I tried it with that but apparently it gives WA to that! It only works if we print ans corr to min area.
2014-04-10 10:28:50 Adrian Satja Kurdija
@ROHIT: Try N = 1309.
2014-04-10 10:28:50 ROHIT RAWAT
@Adrian Satja Kurdija I am getting wrong answer for test case 10. Please tell me how to optimize my code further.
2014-04-10 10:28:50 Hunters Den
The solutions may not be unique.If there are more than one solution, output any.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.