2237. Дом, милый дом @ Timus Online Judge

2237. Дом, милый дом

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ

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

Вначале он выбирает ширину и высоту дома (ниже примеры для 7 × 4 и 6 × 4). Ширина и высота не меньше 3.

Затем он строит «коробку» из блоков — прямоугольник-каркас из блоков дерева (на схеме блоки дерева обозначены символом #).

↑

После этого он заходит внутрь и сносит все «потолочные» блоки, эти блоки возвращаются к нему в полной сохранности (на предыдущей схеме на них указывают символы ↑).

# # # #

# # # #

# # # #

# # # # # # # # # # # # #
Потом он выходит из дома и строит снизу вверх и к центру крышу из деревянных «ступенек», ведь их можно развернуть в обе стороны (на схеме ниже ступеньки из дерева обозначены символами / и \).

Если в конце ему придётся поставить на одно и то же место ступеньку слева и ступеньку справа, то вместо этого он ставит деревянный «полублок» (на схеме ниже полублок из дерева обозначен символом –).

○

В самом конце Вадим оценивает свою работу — подсчитывает количество клеток без блоков внутри дома (на схеме выше эти клетки обозначены символом ∘). Это количество Вадим называет «объёмом».

Как известно каждому игроку, просто так получить ступеньки и полублоки нельзя: их надо скрафтить. Для крафта четырёх ступенек используются шесть блоков дерева, а для крафта шести полублоков используются три блока дерева:

#
#	#		→	/ или \ (4 штуки)
#	#	#

#	#	#	→	- (6 штук)

У Вадима есть T миров, в каждом из которых у него N_i блоков дерева. В каждом мире из блоков он хочет построить дом, наибольший по объёму. Помогите ему найти эти значения, а также размерности домов, при которых эти объёмы достигаются.

Исходные данные

В первой строке ввода даётся целое число T — количество миров (1 ≤ T ≤ 1 000).

В следующих T строках ввода даются целые числа N_i — количество блоков дерева у Вадима в i-м мире (16 ≤ N_i ≤ 10⁹).

Результат

Для каждого мира выведите три целых числа — наибольший возможный объём дома, а также ширину и высоту, на которых этот объём достигается. Гарантируется, что ответ существует. Если ответов несколько, выведите любой из них.

Пример

исходные данные	результат
2 20 30	6 4 3 30 6 7

Автор задачи: Вадим Баринов
Источник задачи: Квалификационный тур Уральского регионального чемпионата ICPC 2026: отбор УрФУ