Representation as Sum of Four Squares

According to Lagrange's Four Square Theorem (also known as the Four Square Theorem), every positive integer can be expressed as the sum of four squares. In fact, if 0 is allowed, every positive integer can be represented as exactly four 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 n, there might be several representations. Your task is to find four non-negative integers \(a, b, c, d\) satisfying the following conditions:

1. \(0 \leq a \leq b \leq c \leq d\).
2. \(a^2 + b^2 + c^2 + d^2 = n\).
3. Among all possible quadruples \((a, b, c, d)\) that satisfy the above, choose the lexicographically smallest one when viewed as a tuple (i.e. sorted in ascending order by \(a, b, c, d\)).

Output the chosen quadruple.

inputFormat

The input consists of a single integer n (\(1 \leq n \leq 10^9\)) representing the number to be expressed as a sum of four squares.

Note: The constraints allow a brute-force solution under the assumption that \(\sqrt{n}\) remains small enough in practice; however, for larger inputs, optimized approaches may be necessary.

outputFormat

Output four non-negative integers \(a, b, c, d\) separated by spaces, which are the lexicographically smallest solution satisfying \(a^2 + b^2 + c^2 + d^2 = n\) and \(0 \leq a \leq b \leq c \leq d\).

sample

5

0 0 1 2