Задача D. Горизонтальные слои квадратов ≡

Условие

Тимофей решил нарисовать прямоугольник по следующим правилам:

Сверху идёт горизонтальный слой квадратов со стороной 1;

Под ним располагается горизонтальный слой квадратов со стороной 2;

...

Последним будет горизонтальный слой квадратов со стороной n.

Определите наименьшие размеры подходящего прямоугольника, полностью заполненного такими квадратами.

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

Единственная строка входных данных содержит натуральное число n — сторону наибольшего квадрата.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите через пробел два натуральных числа — высоту и ширину такого прямоугольника.

Ограничения

2 ≤ n ≤ 40

Пояснение к примерам

Смотри рисунок.

Примеры тестов

2

3 2

3

6 6

4

10 12

Разбор

Высота прямоугольника будет равна сумме чисел от 1 до n или n * (n + 1) // 2, а ширина должна делиться на все числа от 2 до n, то есть это НОК всех чисел от 2 до n.

НОК(a, b) = a * b // НОД(a, b), а НОД можно вычислить с помощью алгоритма Евклида.