Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1574
Pythagorean Triples

Time Limit: 2 Seconds      Memory Limit: 65536 KB

We know there are infinite Pythagorean Triples, such as (3, 4, 5). If (x, y, z) is a Pythagorean Triple and satisfies x < y < z, gcd(x, y, z) = 1, we refer to it as basic Pythagorean Triple. Now we shall sort all basic Pythagorean Triples, first on x, then on y.


Input

One integer each line, 0 < n <= 100,000.


Output

The n-th basic Pythagorean Triple on a line.


Sample Input

1
3


Sample Output

3 4 5
7 24 25



Author: CHEN, Gaoli
Source: ZOJ Monthly, April 2003
Submit    Status