8044 - 四平方和

题目描述

四平方和定理,又称为拉格朗日定理:

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去,就正好可以表示为 4 个数的平方和。

比如:

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

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

对于一个给定的正整数,可能存在多种平方和的表示法。

要求你对 4 个数排序使得 0 \le a \le b \le c \le d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。

输入

程序输入为一个正整数 N(N<5\times10^6)

输出

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

样例

输入

5

输出

0 0 1 2

输入

12

输出

0 2 2 2

输入

773535

输出

1 1 267 838
来源

蓝桥杯 2016 年省赛 A 组 H 题

题目参数
时间限制 3 秒
内存限制 128 MB
提交次数 15
通过人数 8
金币数量 3 枚
难度 基础


上一题 下一题