[AdditionalFile6568.zip](file://AdditionalFile6568.zip?type=additional_file)

#6568. 「Project Euler 9」特殊勾股数

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

一组勾股数由三个自然数组成，$a < b < c$，且

例如，$3^2 + 4^2 = 9 + 16 = 25 = 5^2$。

给出 $N$，请输出所有满足 $a + b + c = N$ 的勾股数。

输入格式

只有一行，一个整数 $N$。

输出格式

多行，每行三个整数，$a, b, c$，表示答案。

样例 1

输入

12

输出

3 4 5

样例 2

输入

120

输出

30 40 50
20 48 52
24 45 51

数据范围与提示

对于 $20\%$ 的数据，$N \leq 5000$。

对于 $40\%$ 的数据，$N \leq 1000000$。

对于 $100\%$ 的数据，$N \leq 10^{12}$。