四方定理

题目背景

四方定理是数论中的著名定理，即任意一个自然数都能拆分成四个自然数的平方之和。例如$25$可表示为$1^{2}+2^{2}+2^{2}+4^{2}$ 、$0^{2}+0^{2}+3^{2}+4^{2}$ 、$0^{2}+0^{2}+0^{2}+5^{2}$等多种形式。

题目描述

给定一个自然数$n$，要求输出$n$的所有四平方拆分方案。

输入格式

一个整数，表示自然数$n$ 。

输出格式

若干行，每行是由从小到大排列的四个自然数组成，代表一种拆分方案。若存在多种方案，按首项从小到大输出；首项相同的，按第二项从小到大输出，以此类推。

数据范围

$0 \leq n \leq 50,000$ 。

样例数据

• 输入

25

• 输出

0 0 0 5
0 0 3 4
1 2 2 4