[edu] Pythagorean triples

A Pythagorean triple (a,b,c)$(a,b,c)$ consists of three strictly positive integers a$a$, b$b$ and c$c$, for which a2+b2=c2$a^2+b^2=c^2$. The name is derived from the Pythagorean theorem, stating that every right triangle has side lengths satisfying the formula a2+b2=c2$a^2+b^2=c^2$. Thus, Pythagorean triples describe the three integer side lengths of a right triangle. However, right triangles with non-integer sides do not form Pythagorean triples.

A well-known example of a Pythagorean triple is (3,4,5)$(3,4,5)$, but also its multiples such as (6,8,10)$(6,8,10)$ and (9,12,15)$(9,12,15)$ are Pythagorean triples. In general, if (a,b,c)$(a,b,c)$ is a Pythagorean triple, then so is (ka,kb,kc)$(ka,kb,kc)$ for any positive integer k$k$. A primitive Pythagorean triple (a,b,c)$(a,b,c)$ is one in which a$a$, b$b$ and c$c$ are coprime. As an example, there are four Pythagorean triples (a,b,c)$(a,b,c)$ for which a+b+c=240$a+b+c=240$: (15,112,113)$(15,112,113)$, (40,96,104)$(40,96,104)$, (48,90,102)$(48,90,102)$ and (60,80,100)$(60,80,100)$.

Pythagorean triples have been known since ancient times.  Babylonian clay tablets dating from the time of Hammurabi already mention Pythagorean triples. The oldest known record comes from Plimpton 322, a Babylonian clay tablet from about 1800BC, written in a sexagesimalnumber system. It was discovered by Edgar James Banks shortly after 1900, and sold to George Arthur Plimpton in 1922 for $10. This clay tablet lists 15 triplets, including (56,90,106)$(56,90,106)$, (119,120,169)$(119,120,169)$ and even (12709,13500,18541)$(12709,13500,18541)$. Pythagorean triples were also known in India. The earliest Baudhayana-Sulbasutra (dating back to the sixth century before Christ) contains five such triples.

Input

A number n∈N0$n\in {\mathbb{N}}_0$.

Output

A list of all Pythagorean triples (a,b,c)$(a,b,c)$ for which 0<a≤b≤c$0<a\le b\le c$ and a+b+c=n$a+b+c=n$. These triples must be written as (a, b, c), each on a separate line and sorted in increasing order according to a$a$, then b$b$ and then c$c$.

Example

Input:

240

Output:

(15, 112, 113)(40, 96, 104)(48, 90, 102)(60, 80, 100)

ver. latest

def check_triple(a, b, c, num):
    cond_pytha = a * a + b * b == c * c
    cond_sum = a + b + c == num
    if cond_pytha and cond_sum:
        return True
    return False


def pick_triple(a, b, c, num):
    if a < b < c:
        if check_triple(a, b, c, num):
            print("({}, {}, {})".format(a, b, c))

def get_triple(num):
    half = int(num / 2)
    for a in range(1, half):
        for b in range(half - a, half):
            for c in range(num - (a + b), half):
                pick_triple(a, b, c, num)

get_triple(int(input()))

def check_pythagorean(a, b, c):
    if a * a + b * b == c * c:
        return True
    else:
        return False


def pick_triple(a, b, c, num, triples):
    if a < b < c:
        if a + b + c == num:
            if check_pythagorean(a, b, c):
                triples.append((a, b, c))


def get_pythagorean(num):
    triples = list()
    half = int(num / 2)
    for a in range(1, half):
        for b in range(half - a, half):
            for c in range(num - (a + b), half):
                pick_triple(a, b, c, num, triples)
    show(triples)


def show(triples):
    for triple in triples:
        print(triple)


get_pythagorean(int(input()))