A. Градостроитель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Таня играет в симулятор градостроителя Cities: Skylines. Новой стратегией развития города стало развитие аграрного сектора, и Таня планирует потратить все оставшиеся деньги в городском бюджете на межевание полей.

Город в игре состоит из маленьких квадратиков со стороной $$$1$$$. Денег в городе осталось ровно на $$$S$$$ таких квадратиков полей.

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

Поля какого размера стоит строить Тане?

Строго говоря, требуется перечислить площади квадратов с целочисленными сторонами, такие что:

  1. Каждый следующий квадрат имеет максимально большую площадь в диапазоне от $$$1$$$ до остатка доступной площади;
  2. Площади всех квадратов в сумме должны давать ровно $$$S$$$.
Входные данные

В первой строке ввода содержится целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 1000$$$).

В каждой из следующих $$$t$$$ строк содержится одно целое число $$$S$$$ $$$(1 \le S \le 10^{17})$$$ — доступная площадь.

Обратите внимание, что число $$$S$$$, а также сам ответ на задачу могут не помещаться в 32-битный целочисленный тип данных. Поэтому при решении этой задачи рекомендуется использовать 64-битный целочисленный тип данных. Например, long long в C++ и int64 в Pascal.

Выходные данные

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

Система оценки
ГруппаДоп. ограниченияБаллыНеобх. подгруппы
$$$S$$$
$$$1$$$$$$S \le 1000$$$$$$30$$$—
$$$2$$$$$$S \le 10^5$$$$$$30$$$$$$1$$$
$$$3$$$—$$$40$$$$$$1$$$, $$$2$$$

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

Пример
Входные данные
3
9
3
63
Выходные данные
9 
1 1 1 
49 9 4 1
Примечание

Разберём по шагам пример, где $$$S = 63$$$.

  • Нам доступна площадь $$$63$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$63$$$ – это квадрат площадью $$$49$$$ (со стороной $$$7$$$). Это легко проверить: если взять квадрат со стороной $$$8$$$, площадь его получится $$$64$$$, что превышает доступную нам площадь.
  • Нам доступна площадь $$$63 - 49 = 14$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$14$$$ – это квадрат площадью $$$9$$$ (со стороной $$$3$$$).
  • Нам доступна площадь $$$14 - 9 = 5$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$5$$$ – это квадрат площадью $$$4$$$ (со стороной $$$2$$$).
  • Нам доступна площадь $$$5 - 4 = 1$$$. Самый большой квадрат, который имеет площадь, не превышающую $$$1$$$ – это квадрат площадью $$$1$$$ (со стороной $$$1$$$).
  • Нам доступна площадь $$$1 - 1 = 0$$$. Мы выбрали все квадраты.

В итоге квадраты в ответе будут $$$49$$$, $$$9$$$, $$$4$$$ и $$$1$$$.