拉格朗日證明了每個正整數都能表示成四個非負整數的平方和。

即著名的四平方和定理。

那麼四次方呢？

所有正整數一定都能分解成 \(53\) 個非負整數的四次方和。

這題就是要請你將輸入的正整數 \(n\) 分解成最多 \(53\) 個非負整數的四次方和。

現在我們來證明這件事是對的：

首先注意到對於任意 \(6\) 的倍數 \(6k\)，我們可以利用四平方和定理將其表示成

\(6k=6(a^2+b^2+c^2+d^2)\)

對 \(a,b,c,d\) 做一樣的事又可得 \(6k=6\left(\left(\sum\limits_{i=1}^4 a_i^2\right)^2+\left(\sum\limits_{i=1}^4 b_i^2\right)^2+\left(\sum\limits_{i=1}^4 c_i^2\right)^2+\left(\sum\limits_{i=1}^4 d_i^2\right)^2\right)\)

接下來考慮恆等式：

\(6\left(\sum\limits_{i=1}^4x_i^2\right)^2=\left(\sum\limits_{i=1}^4\ \sum\limits_{j=1}^{i-1}(x_i+x_j)^4\right)+\left(\sum\limits_{i=1}^4\ \sum\limits_{j=1}^{i-1}(x_i-x_j)^4\right)\)

結合以上我們知道任意的 \(6\) 的倍數都能表示成 \(12\times 4=48\) 個非負整數的四次方和。

因此每個正整數都能表示成 \(48+5=53\) 個非負整數的四次方和，證畢。

若利用 stl::map 可以在 \(O(n\log n)\) 內暴力枚舉出 \(a^2+b^2+c^2+d^2=n\) 的一組非負整數解。

當然，想要的話是可以利用以上證明構造出一組解，但是也可以\(\underline{\textbf{嘗試不用上述方法做這一題}}\)。

Input

輸入一個正整數 \(n\)。

\(1\le n\le 10^{18}\)

Output

第一行輸入一個正整數 \(m\)，須滿足 \(1\le m\le 53\)。

第二行輸出 \(m\) 個非負整數\(x_1,x_2,...,x_m\) ，須滿足 \(0\le x_i\le 31623\) 且 \(x_1^4+x_2^4+...+x_m^4=n\)。

如果有多種答案輸出任意一種就好。

Constraints

第 \(1\) 組測資, \(n\le 10^6\) 且 \(n\) 為 \(6\)的倍數。\((25\text{%})\)

第 \(2\) 組測資, \(n\le 10^6\)。\((25\text{%})\)

第 \(3\) 組測資, \(n\le 10^9\)。\((19\text{%})\)

第 \(4\) 組測資, 沒有其他限制。\((31\text{%})\)

Sample Input 1

18

Sample Output 1

3
1 2 1

Sample Input 2

810

Sample Output 2

10
3 3 3 3 3 3 3 3 3 3

Sample Input 3

1523

Sample Output 3

6
5 1 4 5 2 0

Sample Input 4

7378

Sample Output 4

4
5 4 8 7

Notes

有時候不要太相信題敘，要相信題目難度是照順序排的，不要中毒。