Remote Training on Programming

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

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

·         каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры a × a, b × b и c × c;

·         стороны квадратов должны полностью покрывать дорогу: величина a + b + c должна быть равна n;

·         участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство a < b < c;

·         суммарная площадь участков a² + b² + c² должна быть минимальна.

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

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

Входной файл содержит одно целое число n (6 ≤ n ≤ 10⁹).

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

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

Пример входных и выходных файлов

Входные данные	Выходные данные
6	1 2 3

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

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

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

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

n ≤ 50.

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

n ≤ 2000.

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

n ≤ 40 000.

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

n ≤ 10⁹.

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

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