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 1^{2}, 2^{2}, 3^{2}, ..., N^{2}.
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 N3).
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
hide comments
Petar Bosnjak:
20191127 00:02:40
Is O(n^2*log(n^2)) intended complexity? 

chalarangelo:
20160321 18:30:48
Seems to be too slow using the semibrute force approach. Any ideas on how I could improve it? Also has anyone solved this in Python? 

Ikshu Bhalla:
20140410 10:28:50
@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. 

Adrian Satja Kurdija:
20140410 10:28:50
@ROHIT: Try N = 1309. 

ROHIT RAWAT:
20140410 10:28:50
@Adrian Satja Kurdija I am getting wrong answer for test case 10. Please tell me how to optimize my code further. 

Hunters Den:
20140410 10:28:50
The solutions may not be unique.If there are more than one solution, output any. 
Added by:  Adrian Satja Kurdija 
Date:  20111030 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  that would be me 