Problem Description

The Four Squares Theorem, also called Lagrange's theorem, states:

Every positive integer can be written as the sum of squares of at most $4$ positive integers.

If we also allow $0$, then it can be written as the sum of squares of exactly $4$ numbers.

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 as a sum of squares.

You need to sort the four numbers so that $0 \le a \le b \le c \le d$.

Then sort all possible representations in ascending order using $a,b,c,d$ as a combined key, and finally output the first representation.

Input Format

The input is a positive integer $N(N<5\times10^6)$.

Output Format

Output $4$ non-negative integers in increasing order, separated by spaces.

5

0 0 1 2

12

0 2 2 2

773535

1 1 267 838

Hint

Time limit: 3 seconds, 256M. Lanqiao Cup 2016, the 7th provincial contest.

Lanqiao Cup 2016 provincial contest, Group A Problem H (Group B Problem H).

Translated by ChatGPT 5