Sum of Squares 2 (More Huge)

Time limit0.5sMemory limit512 MB

Summary

Given n up to 10^18, find the minimum number of perfect squares summing to n and output the actual square roots used.

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

Problem

In 1770, Lagrange proved that every natural number can be expressed as a sum of four or fewer squares. Some natural numbers have multiple such representations. For example, 26 is the sum of $5^2$ and $1^2$ ; it can also be written as $4^2 + 3^2 + 1^2$ . Historically, the problem commonly given to mental calculation experts was to express a natural number as a sum of four or fewer squares. In the early 1900s, one mental calculator reportedly took 8 seconds to find the solution $15663 = 125^2 + 6^2 + 1^2 + 1^2$ . A harder problem took 56 seconds: $11339 = 105^2 + 15^2 + 8^2 + 5^2$ .

Given a natural number $n$ , write a computer program that expresses $n$ as a sum of the minimum number of squares.

Input

The input is read from standard input. It consists of one line containing the natural number $n$ , where $1 \le n \le 1{,}000{,}000{,}000{,}000{,}000{,}000$ .

Output

The output is written to standard output. On the first line, print the minimum number of squares whose sum equals $n$ .

On the second line, print the numbers whose squares sum to $n$ , separated by spaces, for as many numbers as printed on the first line. Do not output negative integers.

If there are multiple answers, you may print any of them.

Examples4

Example 1
Input
```
25
```
Expected output
```
1
5
```
Example 2
Input
```
26
```
Expected output
```
2
1 5
```
Example 3
Input
```
11339
```
Expected output
```
3
1 27 103
```
Example 4
Input
```
34567
```
Expected output
```
4
1 22 109 149
```