Source

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

Problem Description

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

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

Input Format

An integer $n$.

Output Format

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

Data Range

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