#7756. 拉格朗日定理 入门

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

比如:

则对于一个给定的正整数  n ,可以表示为: n = a^2 + b^2 + c^2 + d^2 。

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

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

输入格式

输入为一个正整数N (N<5000000)。

输出格式

输出4个非负整数,按从小到大排序,中间用空格分开。

样例

样例输入1

5

样例输出1

0 0 1 2

样例输入2

12

样例输出2

0 2 2 2