Задача E. Три сына ≡

Условие

Во владениях короля Флатландии находится прямая дорога длиной N километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

У короля три сына: младший, средний и старший. Король решил, что в заповедник не войдут участки лесного массива, которые он оставит сыновьям в наследство. При составлении завещания король хочет, чтобы для участков выполнялись следующие условия:

• каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры A × A, B × B и C × C;
• стороны квадратов должны полностью покрывать дорогу: величина A + B + C должна быть равна N;
• участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство A < B < C;
• суммарная площадь участков A² + B² + C² должна быть минимальна.

Требуется написать программу, которая по заданной длине дороги определяет размеры участков, которые следует выделить сыновьям короля.

Формат входного файла

Входной файл содержит одно целое число N.

Формат выходного файла

Выходной файл должен содержать три целых положительных числа, разделенных пробелами: A, B и C — длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

Ограничения

6 ≤ N ≤ 10⁹

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

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Подзадача 1 (25 баллов)

N ≤ 50

Подзадача 2 (25 баллов)

N ≤ 2000

Подзадача 3 (25 баллов)

N ≤ 40 000

Подзадача 4 (25 баллов)

N ≤ 10⁹

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

6

1 2 3