Задача 94. Лютый воевода ≡

Условие

Царь Аарон был ласков до народа,

Да при нем был лютый воевода.

Никого к царю не допускал,

Мужиков порол и обирал;

Добыл рубль — неси ему полтину,

Сыпь в его амбары половину

Изо ржи, пшеницы, конопли;

Мужики ходили наги, босы,

Ни мольбы народа, ни доносы

До царя достигнуть не могли

...

Николай Некрасов, "Сказка о добром царе, злом воеводе и бедном крестьянине", 1877 г.

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

Правила распила такие:

1) Пилить можно только на две или три части.

2) Вес каждой из частей должен выражаться натуральным числом карат. Например, камень весом w = 9 карат можно распилить на части 4 и 5 карат. Или 1, 1 и 7 карат. Или 1, 2 и 6 карат — возможностей много.

3) Поскольку стоимость драгоценного камня вычисляется по формуле p = (w + 1)² рублей (чем крупнее камень, тем реже такие встречаются, соответственно их цена выше), общая стоимость при распиле камня на части неизбежно падает. Зато теперь можно постараться подобрать такой вариант распила, чтобы получившихся камни можно было разделить на две кучки одинаковой стоимости. Например, при w = 9 камень распилят на части весом 2, 3 и 4 карата. Теперь воевода сможет забрать себе ровно половину стоимости — осколок в 4 карата стоит 25 рублей, два осколка в 2 и 3 карата стоят 9 и 16 рублей соответственно, что в сумме опять же составляет те же 25 рублей.

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

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

Единственная строка входного файла содержит натуральное число w — вес алмаза в каратах.

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

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

Ограничения

2 ≤ w ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при четном w, получат не менее 10 баллов.

Решения, верно работающие при w ≤ 100, получат не менее 40 баллов.

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

В первом примере дано w = 3. Есть единственный вариант распила камня на три равные части по 1 карату, но их нельзя разложить на две равные по стоимости кучки, в первой будет один осколок стоимостью 4, во второй — два, общей стоимостью 8.

Второй пример разобран в условии задачи. Это единственное подходящее разделение камня на осколки.

В третьем примере дано w = 57. Есть два подходящих варианта распила камня на три части: 9, 23, 25 и 14, 19, 24. Проверим:

9 + 23 + 25 = 57 и (9 + 1)² + (23 + 1)² = (25 + 1)² = 676.

14 + 19 + 24 = 57 и (14 + 1)² + (19 + 1)² = (24 + 1)² = 625.

Первый способ выгоднее.

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

3

-1

9

2 3 4

57

9 23 25