Задача A. Подарок ≡

Условие

Начинающий программист Поликарп очень любит дарить подарки, особенно в коробках. Он давно заметил, что если коробка красиво оформлена, то радость от подарка возрастает многократно. Любой оберточной бумаге он предпочитает клетчатую. В самом деле, после распаковки подарка на ней можно играть в крестики-нолики, морской бой, точки, а также решать задачи и писать программы.

Поликарп очень аккуратен. Он упаковывает подарок в коробку, имеющую форму прямоугольного параллелепипеда, и оклеивает всю ее поверхность клетчатой бумагой. При этом каждая грань коробки представляет собой прямоугольник, состоящий из целых клеток. На рисунке изображен пример такой упаковки подарка.

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

У Поликарпа в наличии есть лист клетчатой бумаги, состоящий из n клеток. Каким будет максимальный объем коробки, которую можно оклеить с использованием этого листа бумаги описанным выше способом? Поликарп может разрезать лист клетчатой бумаги по границам клеток произвольным образом и оклеивать коробку получившимися фигурами, поэтому форма листа не важна, а имеет значение только количество клеток на нем. Поликарп может использовать для оклеивания коробки не все клетки.

Напишите программу, которая по заданному количеству клеток n находит размеры коробки максимального возможного объема.

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

Входной файл содержит одно целое число n (6 ≤ n ≤ 10¹³) — количество клеток на листе клетчатой бумаги.

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

Выведите в первую строку выходного файла максимальный объем коробки, которую может подарить Поликарп. Объем следует выводить в «кубических клетках», то есть единицей измерения является куб со стороной равной длине стороны клетки.

Во вторую строку выведите ширину, длину и высоту искомой коробки. Единица измерения — размер клетки. Числа разделяйте пробелами. Если решений несколько, то выведите любое из них.

Решения, корректно работающие при n ≤ 5000, будут оцениваться из 30 баллов, а решения, корректно работающие при n ≤ 10⁸, будут оцениваться из 70 баллов.

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

6

1
1 1 1

37

12
3 2 2