Squares

Time limit2sMemory limit1024 MB

Summary

Given N up to 10^18 whose prime factors are all at most 100000, output four non-negative integers whose squares sum to N.

Level: Hard8 of 10
Topics: Number theory, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Jaehong only knows natural numbers up to 100,000. The kind Jonghyuk taught him multiplication, and now Jaehong can also know every natural number that can be made by multiplying numbers up to 100,000.

One day it occurred to Jaehong to write the natural numbers he knows as a sum of the fewest squares. Using the natural numbers up to 100,000 that he already knew, he found that every natural number can be written as a sum of squares using at most 4 squares.

Now Jaehong wants to know whether the large numbers he learned from Jonghyuk can also be written as a sum of four squares. Some of them can be made with fewer than four squares, but for convenience he treats 0 as a square too and will write them as a sum of exactly four squares.

Given a natural number Jaehong knows, write a program that expresses it as a sum of four squares. The expression does not have to use the fewest squares.

Input

The first line gives $N$ ( $1 \le N \le 10^{18}$ ). Every prime factor of $N$ is at most 100,000.

Output

Print four non-negative integers on the first line. The sum of their squares must equal $N$ .

Examples1

Example 1
Input
```
86
```
Expected output
```
3 4 5 6
```