Source

This problem is adapted from Long Long OJ. All rights reserved.

Description

Given an integer $n$, find all valid pairs $(a,b,c)$ consisting of three integers that satisfy the following conditions:

• $1 \leq a \lt b \lt c\leq n$
• $a^{2}+b^{2}=c^{2}$

Input

An integer $n$.

Output

Output all values of $(a,b,c)$ that satisfy the conditions, sorted in lexicographical order from smallest to largest. Separate each number with a space.

Samples

5

3 4 5

20

3 4 5
5 12 13
6 8 10
8 15 17
9 12 15
12 16 20

Tips

For $100\%$ of the testcases, $1\leq n\leq 10^6$.