Problem g: 四平方和

Problem g: 四平方和

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 2366  Solved: 770
[Submit] [Status] [Web Board] [Creator:]

Description

       四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多四个正整数的平方和。如果把0包括进去,就正好可以表示为四个数的平方和。

比如:

5 = 02 + 02 + 12 + 22

7 = 12 + 12 + 12 + 22   

       则对于一个给定的正整数 n,可以表示为:n = a2 + b2 + c2 + d2

       你需要求出字典序最小的一组解a,b,c,d

       字典序大小:从左到右依次比较,如果相同则比较下一项,直到有一项不同,较小的一方字典序更小,反之字典序更大,所有项均相同则二者字典序相同。

Input

程序输入为一个正整数N(1≤N≤5000000)。测试数据只有1组。

Output

输出四个非负整数a,b,c,d中间用空格分开。

Sample Input Copy

【样例输入1】
5
【样例输入2】
12

Sample Output Copy

【样例输出1】
0 0 1 2
【样例输出2】
0 2 2 2