Problem Description

The Four Square Theorem, also known as Lagrange's Theorem:

Every positive integer can be represented as the sum of at most four positive integers' squares.

If we include $0$, it can be exactly represented as the sum of four numbers' squares.

For example:

$5 = 0^2 + 0^2 + 1^2 + 2^2$.

$7 = 1^2 + 1^2 + 1^2 + 2^2$.

For a given positive integer, there may be multiple representations of it as a sum of squares.

You are required to sort the four numbers such that $0 \le a \le b \le c \le d$.

And sort all possible representations by $a, b, c, d$ as the primary keys in ascending order, then output the first representation.

Input Format

The input for the program is a single positive integer $N (N < 5 \times 10^6)$.

Output Format

The output should be four non-negative integers, sorted in ascending order, separated by spaces.

Sample Input and Output

Sample Input #1

5

Sample Output #1

0 0 1 2

Sample Input #2

12

Sample Output #2

0 2 2 2

Sample Input #3

773535

Sample Output #3

1 1 267 838

Notes

Time limit: 3 seconds, Memory limit: 256MB. This problem is from the 7th Lanqiao Cup 2016 Provincial Competition.

This problem is the H question from Group A (Group B) of the 2016 Lanqiao Cup Provincial Competition.

见题面 Input 部分

见题面 Output 部分