Background

四方定理是数论中著名的一个定理，指任意一个自然数都可以拆成四个自然数的平方之和。例如：

$25 = 1^2 + 2^2 + 2^2 + 4^2$

对25来说，还有其他方案：

$25 = 0^2 + 0^2 + 3^2 + 4^2$

以及

$25 = 0^2 + 0^2 +0^2 + 5^2$

Description

给定一个自然数 $n$，请输出 $n$ 的所有四平方拆分方案。

Format

Input

每行一个非负整数n(<=5e6)，不超过10行。

Output

对于每个n，输出若干行：

每行四个由小到大排列的自然数，表示一种拆分方案。

如果有多种方案，按照字典序输出。

Samples

1
25

0 0 0 1
0 0 0 5
0 0 3 4
1 2 2 4

Limitation

1s, 1024KiB for each test case.

Source

YACS 477

2021年8月丙组T3