7503 - 四平方和

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

比如:

• 5 = 0^2 + 0^2 + 1^2 + 2^2

• 7 = 1^2 + 1^2 + 1^2 + 2^2 

即任意给定一个正整数n,都可以表示为: n = a^2 + b^2 + c^2 + d^2。要求求出字典序最小的一组解: a、b、c、d。 

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

输入

一行一个非负整数N(1 ≤ N ≤ 5000000)。

输出

一行四个非负整数,表示a、b、c、d。

样例

输入

5

输出

0 0 1 2

输入

7

输出

1 1 1 2
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题