Найти все возможные значения длины гипотенузы в прямоугольном треугольнике с целыми сторонами, если один из катетов имеет длину p, где p — простое число.


Напоминаем, что простым называется целое положительное число, имеющее ровно два делителя — единицу и самого себя.

Формат ввода


Входные данные содержат одно целое число p (2 ≤ p ≤ 109+9, p — простое).

Формат вывода


Если пифагоровых треугольников с катетом длины p нет, выведите -1. Иначе выведите возможные длины гипотенуз треугольников, перечисленные в порядке возрастания (то есть от меньшей к большей).

Пример

Ввод 3


Вывод 5




Примечания


Пояснение к примеру: cуществует только один целочисленный прямоугольный треугольник с катетом равным 3 — классический пифагоров треугольник c длиной гипотенузы, равной 5.

Решение существует всегда, причем единственное, если p - простое.

Программа на Питоне.

p=int(input())

n=(p*p-1)//2+1

print(n)

import math

p = int(input())

b = False

for i in range(1, p ** 2):

   gip = (p ** 2) + (i ** 2)

   if math.sqrt(gip) % 1 == 0:

       b = True

       if int(math.sqrt(gip)) != p:

           print(int(math.sqrt(gip)))

if b == False:

   print(-1)

# что-то типо этого, но не проходит по времени. Надо смотреть диапазон. Может если кто дорешает, ответьте. а так всё норм работает)